Efficiency in exponential time for domination-type problems

DOI10.1016/j.dam.2008.05.035zbMath1156.05058OpenAlexW1993301031MaRDI QIDQ1003475

Ingo Schiermeyer

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.05.035

zbMATH Keywords

dominationexact algorithmsmatching technique

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Exact algorithms for dominating set ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Exact algorithms for edge domination ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ A refined exact algorithm for edge dominating set ⋮ Inclusion/exclusion meets measure and conquer ⋮ Unnamed Item

Cites Work

• The complexity of colouring problems on dense graphs
• A note on the complexity of the chromatic number problem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• A general method to speed up fixed-parameter-tractable algorithms
• Vertex colouring and forbidden subgraphs -- a survey
• Domination in graphs with minimum degree two
• Algorithms for maximum independent sets
• Paths, Stars and the Number Three
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Spanning trees with many leaves
• On cliques in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficiency in exponential time for domination-type problems