Induced packing of odd cycles in planar graphs

DOI10.1016/j.tcs.2011.11.004zbMath1232.68064MaRDI QIDQ764360

Petr A. Golovach, Dimitrios M. Thilikos, Daniël Paulusma, Marcin Kaminski

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 graphs; fixed parameter tractability; odd cycles; induced packing; irrelevant vertex technique

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Scattered packings of cycles, Negative (and positive) circles in signed graphs: a problem collection, Large Induced Subgraphs via Triangulations and CMSO

Cites Work

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