Computational study for domination problems in planar graphs
Explore this paper's citation graph
Summary
This work develops efficient implementations of algorithms for computing optimal branch-decompositions of planar graphs and proves a better upper bound for the branchwidth in terms of the minimum size of CDS.
- Type
- dissertation
- Published
- 2012-01-31
- Cited by
- 0
- References
- 109
- Access
- Open access
- OpenAlex
- https://openalex.org/W606113
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:115820798
Keywords
Dominating set, Planar graph, Mathematics, Maximal independent set, Approximation algorithm
References
- Fixed Parameter Tractability and Completeness III: Some Structural Aspects of the W Hierarchy
- Fundamentals of domination in graphs
- Approximating the Minimum Maximal Independence Number
- Distributed topology control in wireless ad hoc networks using /spl beta/-skeletons
- Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms
- On algorithms for (P5, gem)-free graphs
- Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set
- Maximal lifetime scheduling in sensor surveillance networks
- Meta-Heuristics: Theory and Applications
- Approximation Algorithms for Treewidth
- Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
- Applications of a planar separator theorem
- Efficient Planarity Testing
- Edge Dominating Sets in Graphs
- The full degree spanning tree problem
- Transitiv orientierbare Graphen
- A threshold of ln n for approximating set cover (preliminary version)
- Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Subexponential parameterized algorithms
Cited by
No citing papers recorded for this paper.
Related papers
- Distributed Dominating Set Approximations beyond Planar Graphs
- Polynomial-time data reduction for dominating set
- A local constant factor approximation for the minimum dominating set problem on bounded genus graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Linear-time algorithms for three domination-based separation problems in block graphs
- Incremental optimization of independent sets under the reconfiguration framework