The NP-completeness column: an ongoing guide
From MaRDI portal
Publication:3747723
DOI10.1016/0196-6774(85)90012-4zbMath0608.68032OpenAlexW4361867857WikidataQ29038371 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
Total domination number of grid graphs ⋮ A theorem on permutation graphs with applications ⋮ A faster algorithm to recognize undirected path graphs ⋮ The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal ⋮ Building a maximal independent set for the vertex-coloring problem on planar graphs ⋮ A heuristic for the coloring of planar graphs ⋮ Finding the minimum bandwidth of an interval graph ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ Bipartite permutation graphs ⋮ Monge matrices make maximization manageable ⋮ Characterizing and recognizing the visibility graph of a funnel-shaped polygon ⋮ The size of \(k\)-pseudotrees ⋮ The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ On locating cubic subgraphs in bounded-degree connected bipartite graphs ⋮ Claw-free graphs---a survey ⋮ Dominating sets whose closed stars form spanning trees ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ Hamiltonian cycles in linear-convex supergrid graphs ⋮ The complexity of optimization problems ⋮ Finding maximum cliques on circular-arc graphs ⋮ Complexity separating classes for edge-colouring and total-colouring ⋮ Trapezoid graphs and their coloring ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ On the complexity of graph reconstruction ⋮ Toughness, hamiltonicity and split graphs ⋮ Independent sets in asteroidal triple-free graphs ⋮ A decomposition strategy for the vertex cover problem ⋮ General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem ⋮ The \(k\)-metric dimension ⋮ Downstream protection value: detecting critical zones for effective fuel-treatment under wildfire risk ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Edge-colouring graphs with bounded local degree sums ⋮ On the complexity of restoring corrupted colorings ⋮ Clustering and outlier detection using isoperimetric number of trees ⋮ Graph coloring with rejection ⋮ On the Structure of Graphs Vertex Critical with Respect to Connected Domination ⋮ Algorithmic expedients for the prize collecting Steiner tree problem ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ A comparison of boundary graph grammars and context-free hypergraph grammars ⋮ Subgraph isomorphism in graph classes ⋮ A sequential algorithm for finding a maximum weightK-independent set on interval graphs ⋮ NP-completeness of edge-colouring some restricted graphs ⋮ Dominating sets in perfect graphs ⋮ Unit disk graphs ⋮ On minimum dominating sets with minimum intersection ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ The (weighted) metric dimension of graphs: hard and easy cases ⋮ Edge colouring line graphs of unicyclic graphs ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ Problems with generalized Steiner problems ⋮ The Hamiltonian properties of supergrid graphs ⋮ Restrictions of graph partition problems. I ⋮ On the equivalence covering number of splitgraphs ⋮ Complete problems for monotone NP ⋮ Coloring temporal graphs ⋮ The Hamiltonian connectivity of rectangular supergrid graphs ⋮ Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ 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 ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ 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 ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Transfer flow graphs ⋮ A note on the Hamiltonian circuit problem on directed path graphs ⋮ Parameterized complexity of vertex colouring ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ The clique-separator graph for chordal graphs ⋮ The Hamiltonian circuit problem for circle graphs is NP-complete ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ Achromatic number is NP-complete for cographs and interval graphs ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ On the algorithmic complexity of twelve covering and independence parameters of graphs ⋮ New heuristic approaches for maximum balanced biclique problem ⋮ Domination number of the cross product of paths ⋮ Revising Johnson's table for the 21st century ⋮ Forests, colorings and acyclic orientations of the square lattice ⋮ The number of nonisomorphic posets having 12 elements ⋮ Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs ⋮ On cocolourings and cochromatic numbers of graphs ⋮ Finding maximum cliques in arbitrary and in special graphs
This page was built for publication: The NP-completeness column: an ongoing guide
