Induced packing of odd cycles in planar graphs
DOI10.1016/J.TCS.2011.11.004zbMATH Open1232.68064OpenAlexW1991178581MaRDI QIDQ764360FDOQ764360
Marcin Kamiński, Petr A. Golovach, Dimitrios M. Thilikos, Daniël Paulusma
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- On the Complexity of General Graph Factor Problems
- Paths, Trees, and Flowers
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Mangoes and blueberries
- Quickly excluding a planar graph
- Odd cycle packing
- Approximation algorithms and hardness results for cycle packing problems
- Induced matchings
- Packing of graphs - a survey
- New results on induced matchings
- The Induced Disjoint Paths Problem
- Induced Packing of Odd Cycles in a Planar Graph
- Title not available (Why is that?)
- An approximation algorithm for maximum triangle packing
- On the induced matching problem
- Even-hole-free graphs. I: Decomposition theorem
- Packing cycles in undirected graphs
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Title not available (Why is that?)
- Even-hole-free graphs part II: Recognition algorithm
- Generalized planar matching
- Odd Hole Recognition in Graphs of Bounded Clique Size
- Approximability of Packing Disjoint Cycles
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Detecting even holes
- On the complexity of testing for odd holes and induced odd paths
- Erratum to ``An approximation algorithm for maximum triangle packing
- Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16--18, 2009. Proceedings
- Edge-packing in planar graphs
- Chordal Deletion Is Fixed-Parameter Tractable
Cited In (8)
- Induced Packing of Odd Cycles in a Planar Graph
- A more accurate view of the flat wall theorem
- Scattered packings of cycles
- Negative (and positive) circles in signed graphs: a problem collection
- Induced odd cycle packing number, independent sets, and chromatic number
- Packing and covering odd cycles in cubic plane graphs with small faces
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
- 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)
