An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

DOI10.1016/j.ipl.2011.02.006zbMath1260.68467OpenAlexW1989856784MaRDI QIDQ1944924

Naoyuki Kamiyama, Keiko Imai, Yusuke Matsumoto

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.02.006

zbMATH Keywords

matchingedge-coloringapproximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)

Related Items

Hardness and approximation of minimum maximal matchings, Decomposition algorithms for solving the minimum weight maximal matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• Parallel concepts in graph theory
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Minimum Edge Dominating Sets
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• Edge Dominating Sets in Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Algorithms and Computation
• Maximum matching and a polyhedron with 0,1-vertices
• Automata, Languages and Programming