The NP-completeness column: an ongoing guide

DOI10.1016/0196-6774(85)90012-4zbMATH Open0608.68032DBLPjournals/jal/Johnson85bOpenAlexW4361867857WikidataQ29038371 ScholiaQ29038371MaRDI QIDQ3747723FDOQ3747723

Authors: D. S. Johnson 

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

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
• 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

zbMATH Keywords

intersection graphsNP-hardnessplanarityperfect graphsnear-trees

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Problems with generalized Steiner problems
• Maximum weightk-independent set problem on permutation graphs
• Dominating sets whose closed stars form spanning trees
• Jump number maximization for proper interval graphs and series-parallel graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Finding maximum cliques on circular-arc graphs
• Labeling algorithms for domination problems in sun-free chordal graphs
• NP-completeness of edge-colouring some restricted graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• Complexity of path-forming games
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Complexity separating classes for edge-colouring and total-colouring
• On the complexity of graph reconstruction
• The complexity of domination problems in circle graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Edge-colouring graphs with bounded local degree sums
• The complexity of optimization problems
• The NP-completeness column: An ongoing guide
• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Subgraph isomorphism in graph classes
• Unit disk graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Claw-free graphs---a survey
• Building a maximal independent set for the vertex-coloring problem on planar graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
• Chromatic index of graphs with no cycle with a unique chord
• Bipartite permutation graphs
• Domination number of the cross product of paths
• Complete problems for monotone NP
• Trapezoid graphs and their coloring
• On the equivalence covering number of splitgraphs
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Dominating sets in perfect graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• The clique-separator graph for chordal graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Finding the minimum bandwidth of an interval graph
• On a graph partition problem with application to VLSI layout
• Paths in interval graphs and circular arc graphs
• Forests, colorings and acyclic orientations of the square lattice
• Hamiltonian cycles in linear-convex supergrid graphs
• On cocolourings and cochromatic numbers of graphs
• Monadic second-order evaluations on tree-decomposable graphs
• Total domination number of grid graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Independent sets in asteroidal triple-free graphs
• Graph coloring with rejection
• The Hamiltonian properties of supergrid graphs
• Parameterized complexity of vertex colouring
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A fully dynamic graph algorithm for recognizing interval graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• A decomposition strategy for the vertex cover problem
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• New heuristic approaches for maximum balanced biclique problem
• The NP-completeness column: An ongoing guide
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• The NP-completeness column: finding needles in haystacks
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Restrictions of graph partition problems. I
• A note on the Hamiltonian circuit problem on directed path graphs
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• On the structure of graphs vertex critical with~respect to connected domination
• Toughness, hamiltonicity and split graphs
• The NP-completeness column: An ongoing guide
• Finding maximum cliques in arbitrary and in special graphs
• Efficient parallel recognition of some circular arc graphs. I
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• The NP-completeness column: An ongoing guide
• Clustering and outlier detection using isoperimetric number of trees
• Edge-colouring and total-colouring chordless graphs
• On minimum dominating sets with minimum intersection
• Edge colouring line graphs of unicyclic graphs
• A faster algorithm to recognize undirected path graphs
• The number of nonisomorphic posets having 12 elements
• Monge matrices make maximization manageable
• Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
• Complexity of maximum cut on interval graphs
• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• The NP-completeness column: An ongoing guide
• Approximability of the path-distance-width for AT-free graphs
• The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal
• The Hamiltonian connectivity of rectangular supergrid graphs
• Computing the clique-separator graph for an interval graph in linear time
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• The size of \(k\)-pseudotrees
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• MaxCut on permutation graphs is NP‐complete
• The overfull conjecture on split-comparability and split-interval graphs
• Spined categories: generalizing tree-width beyond graphs
• The NP-completeness column: An ongoing guide

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 Q3747723)