Some simplified NP-complete graph problems

DOI10.1016/0304-3975(76)90059-1zbMath0338.05120DBLPjournals/tcs/GareyJS76OpenAlexW2030087828WikidataQ56210411 ScholiaQ56210411MaRDI QIDQ1230637

David S. Johnson, Larry J. Stockmeyer, Michael R. Garey

Publication date: 1976

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(76)90059-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)

Related Items (only showing first 100 items - show all)

Hardness results for total rainbow connection of graphs ⋮ Heuristics for the network design problem with connectivity requirements ⋮ Computing role assignments of split graphs ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ A simplified NP-complete MAXSAT problem ⋮ On minimum bisection and related partition problems in graphs with bounded tree width ⋮ Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks ⋮ Approximating minimum \(k\)-section in trees with linear diameter ⋮ On the computational complexity of the virtual network embedding problem ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Mining approximate interval-based temporal dependencies ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ Branch and bound for the cutwidth minimization problem ⋮ Relaxed locally identifying coloring of graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ A computational study and survey of methods for the single-row facility layout problem ⋮ Semidefinite relaxations of ordering problems ⋮ New spectral lower bounds on the bisection width of graphs ⋮ Unbalanced graph partitioning ⋮ A polyhedral approach to the single row facility layout problem ⋮ Computing clique and chromatic number of circular-perfect graphs in polynomial time ⋮ Partitions of graphs into cographs ⋮ The complexity of the empire colouring problem for linear forests ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Parameterized complexity of max-lifetime target coverage in wireless sensor networks ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Lower bounds on the independence number of certain graphs of odd girth at least seven ⋮ The complexity of changing colourings with bounded maximum degree ⋮ Upper bounds on minimum balanced bipartitions ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ Computation of lucky number of planar graphs is NP-hard ⋮ Brooks' theorem for generalized dart graphs ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ Graphs of separability at most 2 ⋮ Iterative denoising ⋮ Optimizing \(K^2\) trees: a case for validating the maturity of network of practices ⋮ A study of 3-arc graphs ⋮ Autonomous sets for the hypergraph of all canonical covers ⋮ A new discrete filled function method for solving large scale max-cut problems ⋮ Complexity results for the gap inequalities for the max-cut problem ⋮ Online maximum \(k\)-coverage ⋮ Robust optimization of graph partitioning involving interval uncertainty ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Expressive markets for donating to charities ⋮ Graph clustering ⋮ Regular inference as vertex coloring ⋮ NP-hardness of the Euclidean Max-Cut problem ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Approximation algorithms for intersection graphs ⋮ The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones ⋮ Computing solutions for matching games ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Gaming is a hard job, but someone has to do it! ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Reconstruction and estimation in the planted partition model ⋮ A GRASP metaheuristic for the robust mapping and routing of dataflow process networks on manycore architectures ⋮ Distance constraints on short cycles for 3-colorability of planar graphs ⋮ Exponential lower bounds for the tree-like Hajós calculus ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ A linear-time algorithm for computing the intersection of all odd cycles in a graph ⋮ Improved approximation algorithms for projection games ⋮ Mixed-integer quadratic programming is in NP ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks ⋮ WORM colorings of planar graphs ⋮ Finite-model theory -- A personal perspective ⋮ MSOL restricted contractibility to planar graphs ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Optimization problems in multiple subtree graphs ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ The algorithmic complexity of mixed domination in graphs ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Computing compatible tours for the symmetric traveling salesman problem ⋮ Maximum information stored in a labeled connected network with minimum edges ⋮ Recolouring-resistant colourings ⋮ Crossing numbers of graphs with rotation systems ⋮ Orthogonal segment stabbing ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ The complexity of finding two disjoint paths with min-max objective function ⋮ Bounded-depth succinct encodings and the structure they imply on graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ Approximating the partition function of planar two-state spin systems ⋮ Base-object location problems for base-monotone regions ⋮ On the extension complexity of combinatorial polytopes ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ Algorithms for the maximum satisfiability problem ⋮ Maximizing edge-ratio is NP-complete ⋮ Convergence and hardness of strategic Schelling segregation ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Connected greedy coloring of \(H\)-free graphs ⋮ On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering ⋮ Chromatic numbers of simplicial manifolds ⋮ On optimal linear arrangements of trees ⋮ On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems

Cites Work

This page was built for publication: Some simplified NP-complete graph problems