Optimization and Recognition for K 5-minor Free Graphs in Linear Time
From MaRDI portal
Publication:5458529
DOI10.1007/978-3-540-78773-0_18zbMATH Open1136.90492OpenAlexW1490056793MaRDI QIDQ5458529FDOQ5458529
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
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_5\)-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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph minors (05C83)
Cites Work
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Applications of a Planar Separator Theorem
- Depth-First Search and Linear Graph Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Graph minors. XIII: The disjoint paths problem
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Über eine Eigenschaft der ebenen Komplexe
- Easy problems for tree-decomposable graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dividing a Graph into Triconnected Components
- Title not available (Why is that?)
- Graph minors. XVI: Excluding a non-planar graph
- Title not available (Why is that?)
- On-line maintenance of triconnected components with SPQR-trees
- 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
- Title not available (Why is that?)
Cited In (13)
- Rooted \(K_4\)-minors
- Tractable minor-free generalization of planar zero-field Ising models
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Maximizing five-cycles in \(K_r\)-free graphs
- A model for finding transition-minors
- NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
- Title not available (Why is that?)
- 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)
