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.
Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
Power network design variants of Steiner Tree are W[1]-hard parameterized by terminals, with XP algorithms for planar low-voltage cases and FPT results under a modified cost model.
citing papers explorer
-
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.
-
Colorful Minors
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
-
Parameterized Complexity of Power Network Design: Coordinating Cable Placement is Hard
Power network design variants of Steiner Tree are W[1]-hard parameterized by terminals, with XP algorithms for planar low-voltage cases and FPT results under a modified cost model.