Introduces TDM-treewidth for graphic matrices with two nonzeros per row and proves polynomial-time solvability for bounded-width integer programs with bounded domains, plus a grid theorem analogue.
Title resolution pending
4 Pith papers cite this work. Polarity classification is still indexing.
citation-role summary
citation-polarity summary
verdicts
UNVERDICTED 4roles
background 1polarities
background 1representative 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.
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.
citing papers explorer
-
Totally $\Delta$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
Introduces TDM-treewidth for graphic matrices with two nonzeros per row and proves polynomial-time solvability for bounded-width integer programs with bounded domains, plus a grid theorem analogue.
-
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.
-
Finding irrelevant vertices in linear time on bounded-genus graphs
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
-
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Model checking for low-monodimensionality fragments of CMSO with disjoint-paths predicate is FPT on topological-minor-free graph classes.