Induced packing of odd cycles in planar graphs

DOI10.1016/J.TCS.2011.11.004MaRDI QIDQ764360zbMATHOpenAlexFDO

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

planar graphsodd cyclesfixed parameter tractabilityinduced packingirrelevant vertex technique

Mathematics Subject Classification ID

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

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

• 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 7051285 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings
• 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
• Induced Packing of Odd Cycles in a Planar Graph
• Induced matchings
• Mangoes and blueberries
• New results on induced matchings
• Odd Hole Recognition in Graphs of Bounded Clique Size
• Odd cycle packing
• 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

(8)

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

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)