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)

• 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
• The \(k\)-metric dimension
• The NP-completeness column: the many limits on approximation
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• Coloring temporal graphs
• Algorithmic expedients for the prize collecting Steiner tree problem
• Polyhedral approach to weighted connected matchings in general graphs
• Directed path graph isomorphism
• A theorem on permutation graphs with applications
• The entropy rounding method in approximation algorithms
• Downstream protection value: detecting critical zones for effective fuel-treatment under wildfire risk
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• Transfer flow graphs
• General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Complexity-separating graph classes for vertex, edge and total colouring
• Hamiltonian cycle is polynomial on cocomparability graphs
• The complexity of coloring games on perfect graphs
• General vertex disjoint paths in series-parallel graphs
• Graph isomorphism is low for PP
• The NP-completeness column: An ongoing guide
• Graph isomorphism is low for PP
• A heuristic for the coloring of planar graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• Revising Johnson's table for the 21st century
• On the complexity of restoring corrupted colorings
• Representations of graphs and networks (coding, layouts and embeddings)
• 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

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)