The NP-completeness column: An ongoing guide
From MaRDI portal
Publication:5896404
DOI10.1016/0196-6774(84)90045-2zbMath0545.68032OpenAlexW4234449555MaRDI QIDQ5896404
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
Analysis of algorithms and problem complexity (68Q25) Problem books (00A07) Graph theory (including graph drawing) in computer science (68R10)
Related Items
An approximation algorithm for clustering graphs with dominating diametral path, Hamiltonian circuits in interval graph generalizations, Bipartite permutation graphs, Solving linear equations parameterized by Hamming weight, On domination problems for permutation and other graphs, Unconstrained multilayer switchbox routing, 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, Domination and total domination on asteroidal triple-free graphs, Total domination in interval graphs, Some polynomially solvable subcases of the detailed routing problem in VLSI design, On approximating the minimum independent dominating set, Fixed edge-length graph drawing is NP-hard, On the algorithmic complexity of twelve covering and independence parameters of graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
