A 2-approximation algorithm for the minimum weight edge dominating set problem
From MaRDI portal
Publication:1602689
DOI10.1016/S0166-218X(00)00383-8zbMath1016.68061MaRDI QIDQ1602689
Hiroshi Nagamochi, Toshihiro Fujito
Publication date: 24 June 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items (35)
Approximation hardness of edge dominating set problems ⋮ Approximating the Minimum Tour Cover with a Compact Linear Program ⋮ A general approximation method for bicriteria minimization problems ⋮ Hardness and approximation of minimum maximal matchings ⋮ Minimum-Cost $$b$$-Edge Dominating Sets on Trees ⋮ New Results on Directed Edge Dominating Set ⋮ New parameterized algorithms for the edge dominating set problem ⋮ Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs ⋮ Graph covering using bounded size subgraphs ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Approximation algorithms for partially covering with edges ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Minimizing maximum weight of subsets of a maximum matching in a bipartite graph ⋮ A primal-dual method for approximating tree cover with two weights ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Covering problems in edge- and node-weighted graphs ⋮ Minimum-cost \(b\)-edge dominating sets on trees ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ Unnamed Item ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Path hitting in acyclic graphs ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Approximating edge dominating set in dense graphs ⋮ The power of the weighted sum scalarization for approximating multiobjective optimization problems ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set ⋮ A Primal-Dual Method for Approximating Tree Cover with Two Weights ⋮ On approximability of the independent/connected edge dominating set problems
Cites Work
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Matching theory
- Optimization, approximation, and complexity classes
- Geometric algorithms and combinatorial optimization
- Parallel concepts in graph theory
- Minimum Edge Dominating Sets
- Edge Dominating Sets in Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Paths, Trees, and Flowers
- Maximum matching and a polyhedron with 0,1-vertices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A 2-approximation algorithm for the minimum weight edge dominating set problem
