The NP-completeness column: an ongoing guide

DOI10.1016/0196-6774(85)90012-4MaRDI QIDQ3747723zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cited in

(only showing first 100 items - show all)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• The number of nonisomorphic posets having 12 elements
• Problems with generalized Steiner problems
• 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
• Maximum weightk-independent set problem on permutation graphs
• Finding maximum cliques on circular-arc graphs
• Monge matrices make maximization manageable
• Labeling algorithms for domination problems in sun-free chordal graphs
• NP-completeness of edge-colouring some restricted graphs
• Further split graphs known to be class 1 and a characterization of subgraph-overfull split graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Complexity of maximum cut on interval graphs
• Complexity of path-forming games
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• The complexity of domination problems in circle graphs
• Complexity separating classes for edge-colouring and total-colouring
• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• Algorithms and complexity of sandwich problems in graphs (extended abstract)
• Achromatic number is NP-complete for cographs and interval graphs
• On the complexity of graph reconstruction
• Edge-colouring graphs with bounded local degree sums
• The complexity of optimization problems
• The NP-completeness column: An ongoing guide
• Subgraph isomorphism in graph classes
• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Approximability of the path-distance-width for AT-free graphs
• The NP-completeness column: An ongoing guide
• Unit disk graphs
• A simple algorithm to find Hamiltonian cycles in proper interval 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
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Claw-free graphs---a survey
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Building a maximal independent set for the vertex-coloring problem on planar graphs
• The size of \(k\)-pseudotrees
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
• MaxCut on permutation graphs is NP‐complete
• The overfull conjecture on split-comparability and split-interval graphs
• Bipartite permutation graphs
• Chromatic index of graphs with no cycle with a unique chord
• Domination number of the cross product of paths
• Complete problems for monotone NP
• Spined categories: generalizing tree-width beyond graphs
• On the equivalence covering number of splitgraphs
• Trapezoid graphs and their coloring
• Dominating sets in perfect graphs
• A comparison of boundary graph grammars and context-free hypergraph grammars
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• The \(k\)-metric dimension
• The NP-completeness column: An ongoing guide
• The clique-separator graph for chordal graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• The NP-completeness column: the many limits on approximation
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• Finding the minimum bandwidth of an interval graph
• On a graph partition problem with application to VLSI layout
• Coloring temporal graphs
• Paths in interval graphs and circular arc graphs
• Forests, colorings and acyclic orientations of the square lattice
• Algorithmic expedients for the prize collecting Steiner tree problem
• Hamiltonian cycles in linear-convex supergrid graphs
• Polyhedral approach to weighted connected matchings in general graphs
• A theorem on permutation graphs with applications
• Monadic second-order evaluations on tree-decomposable graphs
• On cocolourings and cochromatic numbers of graphs
• Total domination number of grid graphs
• The Hamiltonian properties of supergrid graphs
• Graph coloring with rejection
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Directed path graph isomorphism
• Downstream protection value: detecting critical zones for effective fuel-treatment under wildfire risk
• Independent sets in asteroidal triple-free graphs
• The entropy rounding method in approximation algorithms
• Parameterized complexity of vertex colouring
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Transfer flow graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A fully dynamic graph algorithm for recognizing interval graphs
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• New heuristic approaches for maximum balanced biclique problem
• A decomposition strategy for the vertex cover problem
• Complexity-separating graph classes for vertex, edge and total colouring
• Hamiltonian cycle is polynomial on cocomparability graphs
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• The NP-completeness column: An ongoing guide
• Restrictions of graph partition problems. I

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)