Parameterized and approximation algorithms for finding two disjoint matchings

DOI10.1016/j.tcs.2014.03.030zbMath1338.68095OpenAlexW1969297684MaRDI QIDQ300238

Ying Fan, Zhi-Zhong Chen, Lusheng Wang

Publication date: 27 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.03.030

zbMATH Keywords

matchingsapproximation algorithmsfixed-parameter algorithmscolor-codinguniversal sets

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) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• 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
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• Approximating Maximum Edge 2-Coloring in Simple Graphs
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• On Linear Time Minor Tests with Depth-First Search
• Color-coding
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs

This page was built for publication: Parameterized and approximation algorithms for finding two disjoint matchings