Induced packing of odd cycles in planar graphs

DOI10.1016/J.TCS.2011.11.004MaRDI QIDQ764360zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Daniël Paulusma, Dimitrios M. Thilikos, Marcin Kamiński

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.11.004

zbMATH Keywords

fixed parameter tractabilityinduced packingirrelevant vertex techniqueodd cyclesplanar graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Induced Packing of Odd Cycles in a Planar Graph
• Algorithms for finding an induced cycle in planar graphs
• Odd cycle packing
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• Packing cycles in graphs. II

Cites work

• Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• An approximation algorithm for maximum triangle packing
• Approximability of Packing Disjoint Cycles
• Approximation algorithms and hardness results for cycle packing problems
• Chordal Deletion Is Fixed-Parameter Tractable
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Detecting even holes
• Edge-packing in planar graphs
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Erratum to ``An approximation algorithm for maximum triangle packing
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs. I: Decomposition theorem
• Generalized planar matching
• scientific article; zbMATH DE number 5764900 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Induced matchings
• Induced Packing of Odd Cycles in a Planar Graph
• Mangoes and blueberries
• New results on induced matchings
• Odd cycle packing
• Odd Hole Recognition in Graphs of Bounded Clique Size
• On the Complexity of General Graph Factor Problems
• On the complexity of testing for odd holes and induced odd paths
• On the induced matching problem
• Packing cycles in undirected graphs
• Packing of graphs - a survey
• Paths, Trees, and Flowers
• Quickly excluding a planar graph
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• The Induced Disjoint Paths Problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(10)

• Negative (and positive) circles in signed graphs: a problem collection
• Large Induced Subgraphs via Triangulations and CMSO
• Scattered packings of cycles
• Induced Packing of Odd Cycles in a Planar Graph
• Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
• Packing and covering odd cycles in cubic plane graphs with small faces
• Induced odd cycle packing number, independent sets, and chromatic number
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• A more accurate view of the flat wall theorem
• Improved algorithms for perfect graphs and odd holes

This page was built for publication: Induced packing of odd cycles in planar graphs

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