Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

DOI10.1007/978-3-319-03780-6_1zbMath1338.68094OpenAlexW2399828101MaRDI QIDQ2867103

Lusheng Wang, Zhi-Zhong Chen, Ying Fan

Publication date: 10 December 2013

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03780-6_1

zbMATH Keywords

matchingsgraph algorithmsapproximation algorithmsNP-hardnessfixed-parameter algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating maximum edge 2-coloring in simple graphs
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• Approximating the maximum 3-edge-colorable subgraph problem
• Better approximations for max TSP
• Packing \([1, \Delta \)-factors in graphs of small degree]
• An improved randomized approximation algorithm for Max TSP