Buchumschlag

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Chalermsook, Parinya, Kaul, Matthias, Mnich, Matthias, Spoerhase, Joachim, Uniyal, Sumedha, Vaz, Daniel
Format:	Preprint
Veröffentlicht:	2021
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

Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
von: Kaul, Matthias, et al.
Veröffentlicht: (2025)

Shortcuts and Transitive-Closure Spanners Approximation
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2025)

Hardness and Approximation for Coloring Digraphs
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2026)

Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
von: Abbasi, Fateme, et al.
Veröffentlicht: (2023)

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
von: Kaul, Matthias, et al.
Veröffentlicht: (2024)

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
von: Gutin, Gregory, et al.
Veröffentlicht: (2022)

Distributed Sparsest Cut via Eigenvalue Estimation
von: Maus, Yannic, et al.
Veröffentlicht: (2025)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
von: Armbruster, Susanne, et al.
Veröffentlicht: (2024)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Approximating Traveling Salesman Problems Using a Bridge Lemma
von: Böhm, Martin, et al.
Veröffentlicht: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
von: Fischer, David, et al.
Veröffentlicht: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
von: Kolmogorov, Vladimir
Veröffentlicht: (2023)

Optimized 2-Approximation of Treewidth
von: Belbasi, Mahdi, et al.
Veröffentlicht: (2024)

Minimum Stable Cut and Treewidth
von: Lampis, Michael
Veröffentlicht: (2021)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2023)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
von: Dong, Sally, et al.
Veröffentlicht: (2023)

E-Graphs as Circuits, and Optimal Extraction via Treewidth
von: Sun, Glenn, et al.
Veröffentlicht: (2024)

New Diameter Approximations via Distance Oracle Techniques
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

A Broader View on Clustering under Cluster-Aware Norm Objectives
von: Herold, Martin G., et al.
Veröffentlicht: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
von: Herold, Martin G., et al.
Veröffentlicht: (2024)

Going Beyond Surfaces in Diameter Approximation
von: Włodarczyk, Michał
Veröffentlicht: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
von: Mallek, Nadym, et al.
Veröffentlicht: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
von: Ghoshal, Suprovat, et al.
Veröffentlicht: (2026)

Dynamic Treewidth in Logarithmic Time
von: Korhonen, Tuukka
Veröffentlicht: (2025)

Losing Treewidth In The Presence Of Weights
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

Diameter Computation on (Random) Geometric Graphs
von: Bläsius, Thomas, et al.
Veröffentlicht: (2026)

Diameter Shortcut Sets on Temporal Graphs
von: Quantmeyer, Gerome
Veröffentlicht: (2025)

Approximating Small Sparse Cuts
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
von: Aminian, Aida, et al.
Veröffentlicht: (2025)

Sparse Outerstring Graphs Have Logarithmic Treewidth
von: An, Shinwoo, et al.
Veröffentlicht: (2024)