Cover Image

Ghost Value Augmentation for $k$-Edge-Connectivity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hershkowitz, D Ellis, Klein, Nathan, Zenklusen, Rico
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Approximation Schemes for Planar Graph Connectivity Problems
by: Neuwohner, Meike, et al.
Published: (2025)

Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
by: Blauth, Jannis, et al.
Published: (2025)

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

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

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

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
by: Nägele, Martin, et al.
Published: (2026)

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

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

Space Complexity of Vertex Connectivity Oracles
by: Pettie, Seth, et al.
Published: (2022)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

The Steiner Path Aggregation Problem
by: Chen, Da Qi, et al.
Published: (2025)

Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations
by: Liu, Siyue, et al.
Published: (2026)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

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

Low-Step Multi-Commodity Flow Emulators
by: Haeupler, Bernhard, et al.
Published: (2024)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Min-Max Connected Multiway Cut
by: Tiwary, Hans Raj, et al.
Published: (2026)

A Randomized Rounding Approach for DAG Edge Deletion
by: Kalantarzadeh, Sina, et al.
Published: (2025)

On Computing Vertex Connectivity of 1-Plane Graphs
by: Biedl, Therese, et al.
Published: (2022)

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

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

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

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
by: Ingels, Florian, et al.
Published: (2026)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
by: Kita, Nanano
Published: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

$k$-local Graphs
by: Beth, Christian, et al.
Published: (2024)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)