Cover Image

On Sparsest Cut and Conductance in Directed Polymatroidal Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chekuri, Chandra, Louis, Anand
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

Hedgegraph Polymatroids
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Online Disjoint Spanning Trees and Polymatroid Bases
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
by: Chekuri, Chandra, et al.
Published: (2024)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Distributed Sparsest Cut via Eigenvalue Estimation
by: Maus, Yannic, et al.
Published: (2025)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
by: Chekuri, Chandra, et al.
Published: (2024)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
by: Chekuri, Chandra, et al.
Published: (2024)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

Node-Weighted Multicut in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2026)

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

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
by: Harb, Elfarouk, et al.
Published: (2025)

Hypergraph Splitting-Off via Element-Connectivity Preserving Reductions
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
by: Chandrasekaran, Karthekeyan, et al.
Published: (2023)

Uncrossed Multiflows and Applications to Disjoint Paths
by: Chekuri, Chandra, et al.
Published: (2025)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

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

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

Cycle Cancellation for Submodular Fractional Allocations and Applications
by: Chekuri, Chandra, et al.
Published: (2025)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
by: d'Orsi, Tommaso, et al.
Published: (2024)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

Covering a Few Submodular Constraints and Applications
by: Bajpai, Tanvi, et al.
Published: (2025)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Sketching Cuts in Graphs and Hypergraphs
by: Kogan, Dmitry, et al.
Published: (2014)

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Multiway Cuts with a Choice of Representatives
by: Bérczi, Kristóf, et al.
Published: (2024)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Thin Trees for Near Minimum Cuts
by: Klein, Nathan, et al.
Published: (2026)

Local Max-Cut on Sparse Graphs
by: Schwartzman, Gregory
Published: (2023)