Induced packing of odd cycles in planar graphs

DOI10.1016/j.tcs.2011.11.004zbMath1232.68064OpenAlexW1991178581MaRDI 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 graphsfixed parameter tractabilityodd cyclesinduced packingirrelevant vertex technique

Mathematics Subject Classification ID

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

Related Items (3)

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

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