Exact algorithms for edge domination
type: Item
instance of: scholarly article
title: Exact algorithms for edge domination
zbMATH Open document ID: 1264.68211
author: Johan M. M. Van Rooij
author: Hans L. Bodlaender
published in: Algorithmica
publication date: 2013-04-03T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6149491
zbMATH Keywords: edge dominating set
zbMATH Keywords: minimum maximal matching
zbMATH Keywords: exact algorithms
zbMATH Keywords: exponential time algorithms
zbMATH Keywords: measure and conquer
MaRDI profile type: Publication
full work available at URL: s00453-011-9546-x
OpenAlex ID: W2913012475
Wikidata QID: Q59567537
cites work: Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
cites work: Q4699283
cites work: A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
cites work: Q4027320
cites work: Paths, Trees, and Flowers
cites work: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
cites work: A threshold of ln n for approximating set cover
cites work: edge dominating set: Efficient Enumeration-Based Exact Algorithms
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q3396567
cites work: Exact Algorithms for Treewidth and Minimum Fill-In
cites work: On two techniques of combining branching and treewidth
cites work: A measure & conquer approach for the analysis of exact algorithms
cites work: Q5572939
cites work: A Dynamic Programming Approach to Sequencing Problems
cites work: Q3395987
cites work: On generating all maximal independent sets
cites work: Treewidth. Computations and approximations
cites work: New methods for 3-SAT decision and worst-case analysis
cites work: A note on the complexity of the chromatic number problem
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: On cliques in graphs
cites work: Equivalence between the minimum covering problem and the maximum matching problem
cites work: Constrained weighted matchings and edge coverings in graphs
cites work: Efficient exact algorithms through enumerating maximal independent sets and other techniques
cites work: Exact Computation of Maximum Induced Forest
cites work: Algorithms for maximum independent sets
cites work: Efficiency in exponential time for domination-type problems
cites work: STACS 2005
cites work: Finding a Maximum Independent Set
cites work: Algorithms for Vertex Partitioning Problems on Partial k-Trees
cites work: Q4910758
cites work: Inclusion/Exclusion Meets Measure and Conquer
cites work: Q4414647
cites work: Parameterized and Exact Computation
cites work: Edge Dominating Sets in Graphs
DBLP publication ID: journals/algorithmica/RooijB12
DOI: 10.1007/S00453-011-9546-X
description: scientific article; zbMATH DE number 6149491