Computing cut-based hierarchical decompositions in almost linear time

DOI10.1137/1.9781611973402.17MaRDI QIDQ5383976zbMATH OpenOpenAlexFDO

Authors Harald Räcke, Chintan D. Shah, Hanjo Täubig

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.17

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Improved guarantees for tree cut sparsifiers
• Vertex sparsification and oblivious reductions
• Vertex Sparsifiers: New Results from Old Techniques
• Vertex sparsifiers: new results from old techniques
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time

Cited in

(15)

• Improved guarantees for tree cut sparsifiers
• scientific article; zbMATH DE number 1066875 (Why is no real title available?)
• Compact oblivious routing
• Compact oblivious routing in weighted graphs
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Sparse Semi-Oblivious Routing: Few Random Paths Suffice
• Optimal electrical oblivious routing on expanders
• Electrical flows for polylogarithmic competitive oblivious routing
• Deterministic expander routing: faster and more versatile
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
• Practical expander decomposition
• Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts
• Near-optimal directed low-diameter decompositions
• O( n)-approximation algorithms for bipartiteness ratio

This page was built for publication: Computing cut-based hierarchical decompositions in almost linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5383976)