Optimization and Recognition for K 5-minor Free Graphs in Linear Time

DOI10.1007/978-3-540-78773-0_18zbMath1136.90492OpenAlexW1490056793MaRDI QIDQ5458529

Zhentao Li, Bruce A. Reed

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_18

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Rooted \(K_4\)-minors, A model for finding transition-minors, An algorithm for delta-wye reduction of almost-planar graphs, Fast minor testing in planar graphs, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Tractable minor-free generalization of planar zero-field Ising models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Graph minors. XVI: Excluding a non-planar graph
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Graph minors. XIII: The disjoint paths problem
• On-line maintenance of triconnected components with SPQR-trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• A Separator Theorem for Nonplanar Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth