Packing cycles through prescribed vertices under modularity constraints

DOI10.1016/J.AAM.2012.03.002MaRDI QIDQ444427zbMATH OpenOpenAlexFDO

Authors 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

disjoint cycleseven cyclesfeedback vertex setsErdősPósa property

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Packing cycles through prescribed vertices
• Half-integral packing of odd cycles through prescribed vertices
• Long cycles through prescribed vertices have the Erdős-Pósa property
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Disjoint cycles intersecting a set of vertices

Cites work

• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• 2-linked graphs
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Approximation algorithms and hardness results for cycle packing problems
• Disjoint cycles intersecting a set of vertices
• Disjoint paths in graphs
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Graph minors. XIII: The disjoint paths problem
• Highly connected sets and the excluded grid theorem
• On Independent Circuits Contained in a Graph
• On the odd-minor variant of Hadwiger's conjecture
• On the presence of disjoint subgraphs of a specified type
• Packing cycles in undirected graphs
• Packing cycles through prescribed vertices
• Packing cycles with modularity constraints
• Quickly excluding a planar graph

Cited in

(14)

• Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs
• On the presence of disjoint subgraphs of a specified type
• Packing cycles with modularity constraints
• Packing directed cycles through a specified vertex set
• Packing \(A\)-paths of length zero modulo four
• Scattered packings of cycles
• Disjoint cycles intersecting a set of vertices
• A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
• Even A‐cycles have the edge‐Erdős–Pósa property
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Erdős-Pósa property for labeled minors: 2-connected minors
• The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
• Half-integral packing of odd cycles through prescribed vertices
• Packing cycles through prescribed vertices

This page was built for publication: Packing cycles through prescribed vertices under modularity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444427)