An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
From MaRDI portal
Publication:1944924
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
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
