Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs

DOI10.1137/15M1022239zbMath1362.05068MaRDI QIDQ5346553

Naonori Kakimura, Yusuke Kobayashi, Ken-ichi Kawarabayashi

Publication date: 24 May 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Erdős-Pósa propertycycle packingfixed-parameter algorithm

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Packing cycles through prescribed vertices under modularity constraints
• Disjoint cycles intersecting a set of vertices
• Highly parity linked graphs
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Mangoes and blueberries
• Highly connected sets and the excluded grid theorem
• Graph minors. XIII: The disjoint paths problem
• Half-integral packing of odd cycles through prescribed vertices
• Packing cycles through prescribed vertices
• Non-zero disjoint cycles in highly connected group labelled graphs
• On the odd-minor variant of Hadwiger's conjecture
• A shorter proof of the graph minor algorithm
• Edge-disjoint Odd Cycles in 4-edge-connected Graphs
• Long cycles through prescribed vertices have the Erdős‐Pósa property
• Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs
• The Graph Minor Algorithm with Parity Conditions
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity

This page was built for publication: Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs