The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(84)90045-2MaRDI QIDQ5896404zbMATH OpenOpenAlexFDO

Authors D. S. Johnson

Publication date 1984

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(84)90045-2

zbMATH Keywords

dominating setNP-completeness

Mathematics Subject Classification ID

Problem books (00A07) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide

Cited in

(23)

• Hamiltonian circuits in interval graph generalizations
• Bipartite permutation graphs
• On domination problems for permutation and other graphs
• The complexity of minimizing wire lengths in VLSI layouts
• Total domination in interval graphs revisited
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Labeling algorithms for domination problems in sun-free chordal graphs
• Total domination in block graphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Fixed edge-length graph drawing is NP-hard
• Unconstrained multilayer switchbox routing
• Domination and total domination on asteroidal triple-free graphs
• An approximation algorithm for clustering graphs with dominating diametral path
• Solving linear equations parameterized by Hamming weight
• The NP-completeness column: an ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• Total domination in interval graphs
• The NP-completeness column: An ongoing guide
• Some polynomially solvable subcases of the detailed routing problem in VLSI design
• On approximating the minimum independent dominating set
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

This page was built for publication: The NP-completeness column: An ongoing guide

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