Exact Algorithms for Edge Domination

DOI10.1007/978-3-540-79723-4_20MaRDI QIDQ3503591zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Johan M. M. Van Rooij, Hans L. Bodlaender

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.1675

zbMATH Keywords

edge dominating setexact algorithmsexponential time algorithmsmeasure and conquerminimum maximal matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Exact algorithms for edge domination
• A refined exact algorithm for edge dominating set
• A refined exact algorithm for edge dominating set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact algorithms for minimum weighted dominating induced matching

Cites work

• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
• A Dynamic Programming Approach to Sequencing Problems
• A note on the complexity of the chromatic number problem
• A threshold of ln n for approximating set cover
• Algorithms for maximum independent sets
• Automata, Languages and Programming
• Branching and Treewidth Based Exact Algorithms
• Constrained weighted matchings and edge coverings in graphs
• Design by measure and conquer. A faster exact algorithm for dominating set
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Edge Dominating Sets in Graphs
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Exact Algorithms for Edge Domination
• Exact Computation of Maximum Induced Forest
• Finding a Maximum Independent Set
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• scientific article; zbMATH DE number 5604103 (Why is no real title available?)
• scientific article; zbMATH DE number 5605070 (Why is no real title available?)
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• On cliques in graphs
• On generating all maximal independent sets
• Parameterized and Exact Computation
• Quasiconvex analysis of backtracking algorithms
• STACS 2005

Cited in

(19)

• Efficiency in exponential time for domination-type problems
• Improved approximation bounds for edge dominating set in dense graphs
• Exact algorithms for edge domination
• Algorithmic aspects of upper edge domination
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Decomposition algorithms for solving the minimum weight maximal matching problem
• A refined exact algorithm for edge dominating set
• Parameterized edge dominating set in cubic graphs (extended abstract)
• Enumerate and measure: improving parameter budget management
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• Exact Algorithms for Edge Domination
• Parameterized edge dominating set in graphs with degree bounded by 3
• New parameterized algorithms for the edge dominating set problem
• Exact algorithms for dominating set
• A refined exact algorithm for edge dominating set
• The edge domination problem
• An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
• A sharp upper bound for the edge dominating number of hypergraphs with minimum degree
• Parameterized complexity of generalizations of edge dominating set

This page was built for publication: Exact Algorithms for Edge Domination

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