Cover Image

Two-Edge Connectivity via Pac-Man Gluing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Garg, Mohit, Hommelsheim, Felix, Lindermayr, Alexander
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Better-Than-$5/4$-Approximation for Two-Edge Connectivity
by: Hommelsheim, Felix, et al.
Published: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
by: Hommelsheim, Felix, et al.
Published: (2025)

Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
by: Lindermayr, Alexander, et al.
Published: (2026)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints
by: Jäger, Sven, et al.
Published: (2024)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
by: Çivril, Ali
Published: (2024)

Online Flow Time Minimization with Gradually Revealed Jobs
by: Lindermayr, Alexander, et al.
Published: (2026)

Non-Clairvoyant Scheduling with Progress Bars
by: Benomar, Ziyad, et al.
Published: (2025)

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Learning-Augmented Online Scheduling with Parsimonious Preemption
by: Blue, Mugen, et al.
Published: (2026)

Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
by: Lindermayr, Alexander, et al.
Published: (2025)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
by: Kobayashi, Yusuke, et al.
Published: (2026)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Indirect Coflow Scheduling
by: Lindermayr, Alexander, et al.
Published: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
by: Sawettamalya, Pachara, et al.
Published: (2025)

Ghost Value Augmentation for $k$-Edge-Connectivity
by: Hershkowitz, D Ellis, et al.
Published: (2023)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
by: Biedl, Therese, et al.
Published: (2024)

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

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

Improved Approximation Algorithms for the Expanding Search Problem
by: Griesbach, Svenja M., et al.
Published: (2023)

Graph Traversal via Connected Mobile Agents
by: Jana, Saswata, et al.
Published: (2025)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
by: Daga, Mohit
Published: (2025)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

Exact Clique Number Manipulation via Edge Interdiction
by: Zhou, Yi, et al.
Published: (2026)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
by: Jiang, Yonggang, et al.
Published: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
by: Gottesbüren, Lars, et al.
Published: (2025)

Maximizing the Minimum Eigenvalue in Constant Dimension
by: Brown, Adam, et al.
Published: (2024)

Partitioning Trillion Edge Graphs on Edge Devices
by: Chhabra, Adil, et al.
Published: (2024)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)

Thin Trees via $k$-Respecting Cut Identities
by: Daga, Mohit
Published: (2025)