Parameterized and approximation algorithms for finding two disjoint matchings

DOI10.1016/J.TCS.2014.03.030MaRDI QIDQ300238zbMATHOpenAlexFDO

Authors Zhi-Zhong Chen, Ying Fan, 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

approximation algorithmsfixed-parameter algorithmsmatchingscolor-codinguniversal sets

Mathematics Subject Classification ID

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

Recommendations

• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Parameterized algorithms for weighted matching and packing problems
• Matching and \(P _{2}\)-packing: weighted versions
• Parameterized Algorithms for Weighted Matching and Packing Problems
• Matching and weighted \(P_2\)-packing: algorithms and kernels

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3910163 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• An Improved Approximation Algorithm for Maximum Edge 2-Coloring in Simple Graphs
• 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
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Approximating the maximum 3-edge-colorable subgraph problem
• Better approximations for max TSP
• Color-coding
• On Linear Time Minor Tests with Depth-First Search
• Packing \([1, \Delta ]\)-factors in graphs of small degree
• Randomized divide-and-conquer: improved path, matching, and packing algorithms

Cited in

(8)

• Parameterized and approximation complexity of the detection pair problem in graphs
• scientific article; zbMATH DE number 19225 (Why is no real title available?)
• scientific article; zbMATH DE number 2040948 (Why is no real title available?)
• Parameterized algorithms and kernels for almost induced matching
• Sublinear Algorithms for Parameterized Matching
• An efficient algorithm for finding a two-pair, and its applications
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Disjoint stable matchings in linear time

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

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