An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
type: Item
instance of: scholarly article
title: An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
zbMATH Open document ID: 1260.68467
author: Yusuke Matsumoto
author: Naoyuki Kamiyama
author: Keiko Imai
published in: Information Processing Letters
publication date: 2013-03-28T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6149207
zbMATH Keywords: approximation algorithms
zbMATH Keywords: matching
zbMATH Keywords: edge-coloring
MaRDI profile type: Publication
full work available at URL: j.ipl.2011.02.006
OpenAlex ID: W1989856784
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Algorithms and Computation
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: A 2-approximation algorithm for the minimum weight edge dominating set problem
cites work: A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
cites work: Parallel concepts in graph theory
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: Minimum Edge Dominating Sets
cites work: Automata, Languages and Programming
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Q5581642
cites work: Q3870917
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Edge domination on bipartite permutation graphs and cotriangulated graphs
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Edge Dominating Sets in Graphs
DOI: 10.1016/J.IPL.2011.02.006
description: scientific article; zbMATH DE number 6149207