Linear time algorithms for generalized edge dominating set problems

DOI10.1007/S00453-007-9057-YzbMATH Open1141.68058OpenAlexW2136457981MaRDI QIDQ2480902FDOQ2480902

Ojas Parekh, André Berger

Publication date: 3 April 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9057-y

zbMATH Keywords

treesapproximation algorithmedge dominating set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge Dominating Sets in Graphs
• Minimum Edge Dominating Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• On approximability of the independent/connected edge dominating set problems
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• The edge domination problem
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Title not available (Why is that?)
• Approximability of the capacitated \(b\)-edge dominating set problem
• Title not available (Why is that?)

Cited In (12)

• Improved approximation bounds for edge dominating set in dense graphs
• Erratum to: ``Linear time algorithms for generalized edge dominating set problems
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Minimum-cost \(b\)-edge dominating sets on trees
• Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
• Title not available (Why is that?)
• On well-edge-dominated graphs
• Minimum-Cost $$b$$-Edge Dominating Sets on Trees
• Covering problems in edge- and node-weighted graphs
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• On total unimodularity of edge-edge adjacency matrices
• On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem

   Recommendations

• Algorithms and Data Structures 👍 👎
• A 2-approximation algorithm for the minimum weight edge dominating set problem 👍 👎
• Title not available (Why is that?) 👍 👎
• An improved algorithm for parameterized edge dominating set problem 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Linear time algorithms for generalized edge dominating set problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2480902)