Dominating sets and local treewidth

DOI10.1007/B13632MaRDI QIDQ5897248zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Dimitrios M. Thilikos

Publication date 3 March 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b13632

zbMATH Keywords

bounded local treewidthdominating setdomination-treewidth propertyminor-closed graph familytreewidth

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bidimensional Parameters and Local Treewidth
• LATIN 2004: Theoretical Informatics
• scientific article; zbMATH DE number 1617251
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs

Cited in

(10)

• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• Adiabatic quantum programming: minor embedding with hard faults
• Local tree-width, excluded minors, and approximation algorithms
• Locating and total dominating sets in trees
• A refined search tree technique for dominating set on planar graphs
• An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• Bidimensional Parameters and Local Treewidth

This page was built for publication: Dominating sets and local treewidth

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