Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings

DOI10.1007/978-3-319-03780-6_1MaRDI QIDQ2867103zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen, Ying Fan, Lusheng Wang

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

approximation algorithmsfixed-parameter algorithmsgraph algorithmsNP-hardnessmatchings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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
• scientific article; zbMATH DE number 2040948
• scientific article; zbMATH DE number 19225
• scientific article; zbMATH DE number 1305475
• Sublinear Algorithms for Parameterized Matching
• Complexity of a disjoint matching problem on bipartite graphs
• Parameterized algorithms for inclusion of linear matchings
• Approximating matchings in parallel
• Approximation algorithms for bipartite matching with metric and geometric costs
• An Improved Parameterized Algorithm for a Generalized Matching Problem

Cites work

• scientific article; zbMATH DE number 3910163 (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
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Approximating the maximum 3-edge-colorable subgraph problem
• Approximation algorithms for NP-hard problems.
• Better approximations for max TSP
• Packing \([1, \Delta ]\)-factors in graphs of small degree

Cited in

(8)

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

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 Q2867103)