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 graphsnear-treesNP-hardnessperfect graphsplanarity

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)

• The clique-separator graph for chordal graphs
• 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
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• The Hamiltonian connectivity of rectangular supergrid graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• 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
• Algorithmic expedients for the prize collecting Steiner tree problem
• A fully dynamic graph algorithm for recognizing interval graphs
• Revising Johnson's table for the 21st century
• 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
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• General swap-based multiple neighborhood adaptive search for the maximum balanced biclique problem
• Complexity-separating graph classes for vertex, edge and total colouring
• Edge-colouring graphs with bounded local degree sums
• Coloring temporal graphs
• Chromatic index of graphs with no cycle with a unique chord
• A faster algorithm to recognize undirected path graphs
• Complexity separating classes for edge-colouring and total-colouring
• The \(k\)-metric dimension
• On the complexity of restoring corrupted colorings
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Computing the clique-separator graph for an interval graph in linear time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Downstream protection value: detecting critical zones for effective fuel-treatment under wildfire risk
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• On the structure of graphs vertex critical with~respect to connected domination
• Approximability of the path-distance-width for AT-free graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• Edge-colouring and total-colouring chordless graphs
• On the complexity of graph reconstruction
• Maximum weightk-independent set problem on permutation graphs
• Subgraph isomorphism in graph classes
• Independent sets in asteroidal triple-free graphs
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• An explicit construction of optimal dominating and [1, 2]–dominating sets in grid
• The NP-completeness column: the many limits on approximation
• The NP-completeness column: finding needles in haystacks
• The Hamiltonian properties of supergrid graphs
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Graph isomorphism is low for PP
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• The entropy rounding method in approximation algorithms
• 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

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)