The NP-completeness column: an ongoing guide
From MaRDI portal
Publication:3747723
DOI10.1016/0196-6774(85)90012-4zbMath0608.68032WikidataQ29038371 ScholiaQ29038371MaRDI QIDQ3747723
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90012-4
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
On the complexity of graph reconstruction, Maximum weightk-independent set problem on permutation graphs, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, Restrictions of graph partition problems. I, On the equivalence covering number of splitgraphs, Complete problems for monotone NP, Monadic second-order evaluations on tree-decomposable graphs, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Finding maximum cliques in arbitrary and in special graphs, Recognizing and representing proper interval graphs in parallel using merging and sorting, A comparison of boundary graph grammars and context-free hypergraph grammars, Finding the minimum bandwidth of an interval graph, Bipartite permutation graphs, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, The complexity of optimization problems, Finding maximum cliques on circular-arc graphs, Trapezoid graphs and their coloring, Labeling algorithms for domination problems in sun-free chordal graphs, A decomposition strategy for the vertex cover problem, NP-completeness of edge-colouring some restricted graphs, Dominating sets in perfect graphs, Unit disk graphs, On minimum dominating sets with minimum intersection, Representations of graphs and networks (coding, layouts and embeddings), Edge colouring line graphs of unicyclic graphs, Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Problems with generalized Steiner problems, Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm, On a graph partition problem with application to VLSI layout, An efficient algorithm for finding a maximum weight 2-independent set on interval graphs, Hamiltonian cycle is polynomial on cocomparability graphs, The complexity of coloring games on perfect graphs, General vertex disjoint paths in series-parallel graphs, The complexity of domination problems in circle graphs, Efficient parallel recognition of some circular arc graphs. I, Graph isomorphism is low for PP, Complexity of path-forming games, Paths in interval graphs and circular arc graphs, A note on the Hamiltonian circuit problem on directed path graphs, Weighted connected domination and Steiner trees in distance-hereditary graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, Domination number of the cross product of paths, Forests, colorings and acyclic orientations of the square lattice, The number of nonisomorphic posets having 12 elements, On cocolourings and cochromatic numbers of graphs, A theorem on permutation graphs with applications, On locating cubic subgraphs in bounded-degree connected bipartite graphs, Claw-free graphs---a survey, Dominating sets whose closed stars form spanning trees, Total domination number of grid graphs, Transfer flow graphs, Parameterized complexity of vertex colouring, Jump number maximization for proper interval graphs and series-parallel graphs, The Hamiltonian circuit problem for circle graphs is NP-complete, Achromatic number is NP-complete for cographs and interval graphs, Monge matrices make maximization manageable, Characterizing and recognizing the visibility graph of a funnel-shaped polygon, The size of \(k\)-pseudotrees, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, Toughness, hamiltonicity and split graphs, A faster algorithm to recognize undirected path graphs, Approximating the minimum clique cover and other hard problems in subtree filament graphs, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, A sequential algorithm for finding a maximum weightK-independent set on interval graphs
