Image de couverture de livre

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chen, Yu, Tan, Zihan
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Lower Bounds on Flow Sparsifiers with Steiner Nodes
par: Chen, Yu, et autres
Publié: (2026)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
par: Zhao, Yibin
Publié: (2025)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
par: Das, Syamantak, et autres
Publié: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
par: Anand, Aditya, et autres
Publié: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
par: Khanna, Sanjeev, et autres
Publié: (2024)

Dynamic Kernel Graph Sparsifiers
par: Cao, Yang, et autres
Publié: (2022)

Paths and Intersections: Exact Emulators for Planar Graphs
par: Li, George Z., et autres
Publié: (2025)

Sparsifying Cayley Graphs on Every Group
par: Hsieh, Jun-Ting, et autres
Publié: (2025)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
par: Chen, Yu, et autres
Publié: (2023)

New Oracles and Labeling Schemes for Vertex Cut Queries
par: Jiang, Yonggang, et autres
Publié: (2025)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
par: Chen, Yu, et autres
Publié: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
par: Basu, Arpon, et autres
Publié: (2025)

Lower Bounds on $0$-Extension with Steiner Nodes
par: Chen, Yu, et autres
Publié: (2024)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
par: Chuzhoy, Julia, et autres
Publié: (2025)

Improved Tree Sparsifiers in Near-Linear Time
par: Agassy, Daniel, et autres
Publié: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
par: Chuzhoy, Julia, et autres
Publié: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

Cluster Vertex Deletion on Chordal Graphs
par: Cao, Yixin, et autres
Publié: (2026)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
par: Dughmi, Shaddin, et autres
Publié: (2025)

Multiplicative Spanners in Minor-Free Graphs
par: Bodwin, Greg, et autres
Publié: (2025)

Twice-Ramanujan Sparsifiers
par: Batson, Joshua, et autres
Publié: (2008)

Many Hamiltonians Are Sparsifiable
par: Basu, Arpon, et autres
Publié: (2026)

Query Complexity of the Metric Steiner Tree Problem
par: Chen, Yu, et autres
Publié: (2022)

Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
par: Klemz, Boris, et autres
Publié: (2024)

The Connected k-Vertex One-Center Problem on Graphs
par: Zhang, Jingru
Publié: (2024)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
par: Neiman, Ofer, et autres
Publié: (2026)

Sketching Cuts in Graphs and Hypergraphs
par: Kogan, Dmitry, et autres
Publié: (2014)

Approximate Light Spanners in Planar Graphs
par: Le, Hung, et autres
Publié: (2025)

Distances in Planar Graphs are Almost for Free!
par: Mozes, Shay, et autres
Publié: (2026)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
par: Khanna, Sanjeev, et autres
Publié: (2024)

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
par: Peng, Pan, et autres
Publié: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
par: Balakrishnan, Girish, et autres
Publié: (2024)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
par: Fischer, Olivier, et autres
Publié: (2025)

Local Max-Cut on Sparse Graphs
par: Schwartzman, Gregory
Publié: (2023)

Algebraic Vertex Ordering of a Sparse Graph for Adjacency Access Locality and Graph Compression
par: Floros, Dimitris, et autres
Publié: (2024)

Approximation Schemes for Planar Graph Connectivity Problems
par: Neuwohner, Meike, et autres
Publié: (2025)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
par: Gharan, Shayan Oveis, et autres
Publié: (2025)

Enumeration kernels for Vertex Cover and Feedback Vertex Set
par: Bougeret, Marin, et autres
Publié: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
par: Chang, Hsien-Chih, et autres
Publié: (2024)

New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
par: Heck, Sophia, et autres
Publié: (2026)