Exact Algorithms for Edge Domination

DOI10.1007/978-3-540-79723-4_20zbMath1142.68601OpenAlexW1531307275WikidataQ59567731 ScholiaQ59567731MaRDI QIDQ3503591

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

exact algorithmsedge dominating setexponential time algorithmsmeasure and conquerminimum maximal matching

Mathematics Subject Classification ID

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

Related Items (9)

An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set ⋮ Parameterized edge dominating set in graphs with degree bounded by 3 ⋮ New parameterized algorithms for the edge dominating set problem ⋮ Exact Algorithms for Edge Domination ⋮ Exact algorithms for dominating set ⋮ Parameterized Edge Dominating Set in Cubic Graphs ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• A note on the complexity of the chromatic number problem
• Constrained weighted matchings and edge coverings in graphs
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• A threshold of ln n for approximating set cover
• A Dynamic Programming Approach to Sequencing Problems
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact Algorithms for Edge Domination
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Algorithms for maximum independent sets
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Edge Dominating Sets in Graphs
• Finding a Maximum Independent Set
• Parameterized and Exact Computation
• Branching and Treewidth Based Exact Algorithms
• Quasiconvex Analysis of Backtracking Algorithms
• STACS 2005
• Automata, Languages and Programming
• Exact Computation of Maximum Induced Forest
• On cliques in graphs
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

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