On approximability of the independent/connected edge dominating set problems

DOI10.1016/S0020-0190(01)00138-7zbMath1032.68120MaRDI QIDQ1603390

Toshihiro Fujito

Publication date: 14 July 2002

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

zbMATH Keywords

Approximation algorithmsCombinatorial optimization problemsEdge dominating set

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

A metaheuristic approach to the dominating tree problem ⋮ PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs ⋮ Graph covering using bounded size subgraphs ⋮ On approximation of dominating tree in wireless sensor networks ⋮ A primal-dual method for approximating tree cover with two weights ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ The price of connectivity for cycle transversals ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the minimum maximal independence number
• Approximating the tree and tour covers of a graph
• On approximating the minimum independent dominating set
• Depth-first search and the vertex cover problem
• Geometric algorithms and combinatorial optimization
• Parallel concepts in graph theory
• Approximation algorithms for connected dominating sets
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• An analysis of the greedy algorithm for the submodular set covering problem
• Edge Dominating Sets in Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees

This page was built for publication: On approximability of the independent/connected edge dominating set problems