Buchumschlag

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Çivril, Ali
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
von: Çivril, Ali
Veröffentlicht: (2023)

4/3-Approximation of Graphic TSP
von: Çivril, Ali
Veröffentlicht: (2023)

3/2-Approximation for the Forest Augmentation Problem
von: Çivril, Ali
Veröffentlicht: (2024)

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
von: Hommelsheim, Felix, et al.
Veröffentlicht: (2025)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2026)

Two-Edge Connectivity via Pac-Man Gluing
von: Garg, Mohit, et al.
Veröffentlicht: (2024)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
von: Long, Yaowei, et al.
Veröffentlicht: (2024)

Space Complexity of Vertex Connectivity Oracles
von: Pettie, Seth, et al.
Veröffentlicht: (2022)

The Connected k-Vertex One-Center Problem on Graphs
von: Zhang, Jingru
Veröffentlicht: (2024)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
von: Fischer, Olivier, et al.
Veröffentlicht: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
von: Bhanja, Koustav, et al.
Veröffentlicht: (2025)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
von: Li, Xizhe, et al.
Veröffentlicht: (2026)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
von: Georgiadis, Loukas, et al.
Veröffentlicht: (2026)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Connectivity Oracles for Predictable Vertex Failures
von: Hu, Bingbing, et al.
Veröffentlicht: (2023)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2022)

FPT Approximations for Connected Maximum Coverage
von: Inamdar, Tanmay, et al.
Veröffentlicht: (2026)

Approximation Algorithms for Steiner Connectivity Augmentation
von: Hathcock, Daniel, et al.
Veröffentlicht: (2023)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Approximating Directed Connectivity in Almost-Linear Time
von: Quanrud, Kent
Veröffentlicht: (2025)

Approximation Schemes for Planar Graph Connectivity Problems
von: Neuwohner, Meike, et al.
Veröffentlicht: (2025)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
von: Blikstad, Joakim, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
von: D'Angelo, Gianlorenzo, et al.
Veröffentlicht: (2025)

On Computing Vertex Connectivity of 1-Plane Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2022)

Weighted Partition Vertex and Edge Cover
von: Dabas, Rajni, et al.
Veröffentlicht: (2025)

A Radius-Sensitive Approximation Algorithm for Connected Submodular Maximization
von: Cervenjak, Philip, et al.
Veröffentlicht: (2026)

Streaming Algorithms for Connectivity Augmentation
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
von: Sawettamalya, Pachara, et al.
Veröffentlicht: (2025)

Capacitated Partition Vertex Cover and Partition Edge Cover
von: Dabas, Rajni, et al.
Veröffentlicht: (2025)

Approximating Optimal Labelings for Temporal Connectivity
von: Carnevale, Daniele, et al.
Veröffentlicht: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
von: German, Samuel
Veröffentlicht: (2026)

Caching Connections in Matchings
von: Sadeh, Yaniv, et al.
Veröffentlicht: (2023)