Buchumschlag

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Liao, Chao, Chen, Qingyun, Laekhanukit, Bundit, Zhang, Yuhao
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms Computational Complexity Optimization and Control 68Q17 F.2.2; G.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
von: Chen, Yijia, et al.
Veröffentlicht: (2023)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
von: Laekhanukit, Bundit
Veröffentlicht: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
von: Jain, Rahul, et al.
Veröffentlicht: (2019)

Almost Tight Additive Guarantees for $k$-Edge-Connectivity
von: Kumar, Nikhil, et al.
Veröffentlicht: (2025)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

On Small-depth Frege Proofs for PHP
von: Håstad, Johan
Veröffentlicht: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
von: Levin, Leonid A.
Veröffentlicht: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
von: Eua-anant, Pakapim, et al.
Veröffentlicht: (2025)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
von: Grochow, Joshua A., et al.
Veröffentlicht: (2025)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

DAG Scheduling in the BSP Model
von: Papp, Pál András, et al.
Veröffentlicht: (2023)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
von: Hoang, Hung P., et al.
Veröffentlicht: (2026)

Pliability and Approximating Max-CSPs
von: Romero, Miguel, et al.
Veröffentlicht: (2019)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
von: DasGupta, Bhaskar, et al.
Veröffentlicht: (2026)

Large cliques and large independent sets: can they coexist?
von: Feige, Uriel, et al.
Veröffentlicht: (2025)

Mim-Width is paraNP-complete
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Answering Related Questions
von: Bonnet, Édouard
Veröffentlicht: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
von: Philip, Geevarghese, et al.
Veröffentlicht: (2026)

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
von: Moseley, Benjamin, et al.
Veröffentlicht: (2026)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
von: Dvořák, Pavel, et al.
Veröffentlicht: (2017)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
von: Kowaluk, Miroslaw, et al.
Veröffentlicht: (2025)

Parallel Algorithms for Group Isomorphism via Code Equivalence
von: Levet, Michael
Veröffentlicht: (2026)

Overlapping Biclustering
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
von: Kullmann, Oliver, et al.
Veröffentlicht: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
von: Levet, Michael, et al.
Veröffentlicht: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
von: Levet, Michael, et al.
Veröffentlicht: (2023)

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
von: Lobe, Elisabeth, et al.
Veröffentlicht: (2021)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
von: Huber, Michael Kiran
Veröffentlicht: (2024)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
von: Morse, Gregory, et al.
Veröffentlicht: (2026)

Graph Threading with Turn Costs
von: Demaine, Erik D., et al.
Veröffentlicht: (2024)

Realizing temporal graphs from fastest travel times
von: Klobas, Nina, et al.
Veröffentlicht: (2023)

A Piecewise Approach for the Analysis of Exact Algorithms
von: Clinch, Katie, et al.
Veröffentlicht: (2024)

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
von: Sarriguren, Alfredo Goñi
Veröffentlicht: (2024)

Interval Graphs are Reconstructible
von: Heinrich, Irene, et al.
Veröffentlicht: (2025)

A New Temporal Interpretation of Cluster Editing
von: Bocci, Cristiano, et al.
Veröffentlicht: (2022)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
von: Bell, Tolson, et al.
Veröffentlicht: (2024)