The Graph Minor Algorithm with Parity Conditions

DOI10.1109/FOCS.2011.52MaRDI QIDQ5494959zbMATH OpenWikidataFDO

Authors Ken-ichi Kawarabayashi, Paul Wollan, Bruce Reed

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.52

Mathematics Subject Classification ID

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

Cited in

(17)

• Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• Claw-free t-perfect graphs can be recognized in polynomial time
• Single commodity-flow algorithms for lifts of graphic and cographic matroids
• Tight cycle relaxations for the cut polytope
• Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Chordless Cycle Packing Is Fixed-Parameter Tractable
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Tight bounds for divisible subdivisions
• Dynamic programming on bipartite tree decompositions
• Decremental sensitivity oracles for covering and packing minors
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Dynamic programming on bipartite tree decompositions
• The Even-Path problem in directed single-crossing-minor-free graphs
• Hitting meets packing: how hard can it be?

This page was built for publication: The Graph Minor Algorithm with Parity Conditions

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