Exact algorithms for edge domination

DOI10.1007/s00453-011-9546-xzbMath1264.68211OpenAlexW2913012475WikidataQ59567537 ScholiaQ59567537MaRDI QIDQ1945174

Johan M. M. van Rooij, Hans L. Bodlaender

Publication date: 3 April 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9546-x

zbMATH Keywords

exact algorithmsedge dominating setexponential time algorithmsmeasure and conquerminimum maximal matching

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

A multivariate framework for weighted FPT algorithms ⋮ Exact algorithms for maximum induced matching ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ A refined exact algorithm for edge dominating set ⋮ Inclusion/exclusion meets measure and conquer ⋮ Unnamed Item ⋮ Inexact graph matching using a hierarchy of matching processes ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set ⋮ The Multi-parameterized Cluster Editing Problem ⋮ Exact algorithms for dominating induced matching based on graph partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficiency in exponential time for domination-type problems
• On two techniques of combining branching and treewidth
• Equivalence between the minimum covering problem and the maximum matching problem
• On generating all maximal independent sets
• A note on the complexity of the chromatic number problem
• Constrained weighted matchings and edge coverings in graphs
• Treewidth. Computations and approximations
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• New methods for 3-SAT decision and worst-case analysis
• Efficient exact algorithms through enumerating maximal independent sets and other techniques
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A threshold of ln n for approximating set cover
• A Dynamic Programming Approach to Sequencing Problems
• A measure & conquer approach for the analysis of exact algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact Algorithms for Treewidth and Minimum Fill-In
• Inclusion/Exclusion Meets Measure and Conquer
• 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
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Parameterized and Exact Computation
• Paths, Trees, and Flowers
• STACS 2005
• Graph-Theoretic Concepts in Computer Science
• 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