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

DOI10.1007/978-3-540-78773-0_18MaRDI QIDQ5458529zbMATH OpenOpenAlexFDO

Authors Zhentao Li, Bruce 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 algorithms (graph-theoretic aspects) (05C85) Graph minors (05C83)

Recommendations

• Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
• The linear arboricity of \(K_5\)-minor free graphs
• Coloring algorithms for \(K_ 5\)-minor free graphs
• Choosability of K₅-minor-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• The total coloring of \(K_5\)-minor-free graphs
• scientific article; zbMATH DE number 1979505
• Maximizing five-cycles in \(K_r\)-free graphs
• The Alon-Tarsi number of \(K_5\)-minor-free graphs
• 5-coloring \(K_{3,k}\)-minor-free graphs

Cites work

• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• scientific article; zbMATH DE number 742981 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Depth-First Search and Linear Graph Algorithms
• Dividing a Graph into Triconnected Components
• Easy problems for tree-decomposable graphs
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Fast separation in a graph with an excluded minor
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Graph minors. XX: Wagner's conjecture
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On-line maintenance of triconnected components with SPQR-trees
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(14)

• Rooted K₄-minors
• A linear-time algorithm to find a separator in a graph excluding a minor
• scientific article; zbMATH DE number 742981 (Why is no real title available?)
• Tractable minor-free generalization of planar zero-field Ising models
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Fast minor testing in planar graphs
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Maximizing five-cycles in \(K_r\)-free graphs
• A model for finding transition-minors
• scientific article; zbMATH DE number 1979505 (Why is no real title available?)
• scientific article; zbMATH DE number 140499 (Why is no real title available?)
• An algorithm for delta-wye reduction of almost-planar graphs
• Fundamentals of Computation Theory

This page was built for publication: Optimization and Recognition for K 5-minor Free Graphs in Linear Time

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