The work defines separated low-diameter decompositions for directed graphs and proves the first sub-logarithmic diameter guarantees via small modifications to two prior algorithms.
Hardness of approxi- mation in p via short cycle removal: cycle detection, distance oracles, and beyond
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
citing papers explorer
-
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
The work defines separated low-diameter decompositions for directed graphs and proves the first sub-logarithmic diameter guarantees via small modifications to two prior algorithms.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.