Packing cycles exactly in polynomial time

DOI10.1007/s10878-010-9347-1zbMath1242.90190OpenAlexW2057309492MaRDI QIDQ421271

Xu-jin Chen, Qin Chen

Publication date: 23 May 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9347-1

zbMATH Keywords

polynomial algorithmmin-max relationpacking and coveringmaximum cycle packing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Packing cycles in graphs
• Packing cycles in graphs. II
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Combinatorial Optimization
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• 2-Matchings and 2-covers of hypergraphs
• Approximation algorithms and hardness results for cycle packing problems
• On Independent Circuits Contained in a Graph
• Combinatorial optimization. Theory and algorithms.