scientific article; zbMATH DE number 2089221

MaRDI QIDQ3046490zbMATH OpenFDO

Authors

Publication date 12 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2368/23680180.htm

zbMATH Keywords

dominating setfixed parameter algorithmgenusgraph

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) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• Genus characterizes the complexity of certain graph problems: Some tight results
• Automata, Languages and Programming

Cited in

(4)

• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• scientific article; zbMATH DE number 2038759 (Why is no real title available?)
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Automata, Languages and Programming

This page was built for publication:

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