Packing cycles through prescribed vertices under modularity constraints

DOI10.1016/j.aam.2012.03.002zbMath1245.05102MaRDI QIDQ444427

Naonori Kakimura, Ken-ichi Kawarabayashi

Publication date: 14 August 2012

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aam.2012.03.002

zbMATH Keywords

even cycles; disjoint cycles; Erdős; feedback vertex sets; Pósa property

Mathematics Subject Classification ID

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

05C38: Paths and cycles

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

Related Items

Erdös--Pósa Property for Labeled Minors: 2-Connected Minors, Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs, Unnamed Item, Even A‐cycles have the edge‐Erdős–Pósa property, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs, Half-integral packing of odd cycles through prescribed vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Packing cycles with modularity constraints
• Disjoint cycles intersecting a set of vertices
• Disjoint paths in graphs
• 2-linked graphs
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Packing cycles through prescribed vertices
• On the odd-minor variant of Hadwiger's conjecture
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• On the presence of disjoint subgraphs of a specified type
• Packing cycles in undirected graphs
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Approximation algorithms and hardness results for cycle packing problems
• On Independent Circuits Contained in a Graph