Some simplified NP-complete graph problems

DOI10.1016/0304-3975(76)90059-1zbMath0338.05120OpenAlexW2030087828WikidataQ56210411 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

Superposition and constructions of graphs without nowhere-zero $k$-flows, Complexity of finding dense subgraphs, Algorithmic complexity of list colorings, On the complexity of barrier resilience for fat regions and bounded ply, A graph approximation heuristic for the vertex cover problem on planar graphs, Call routing and the ratcatcher, The hardness of approximation: Gap location, On problems with short certificates, HV-planarity: algorithms and complexity, New heuristic solution procedures for the uniform graph partitioning problem: Extensions and evaluation, A genetic algorithm for the talent scheduling problem, On approximation algorithms for the minimum satisfiability problem, On piecewise quadratic Newton and trust region problems, A linear programming approach to reasoning about probabilities, $k$-edge subgraph problems, Improved exact approaches for row layout problems with departments of equal length, An exact algorithm for min-max hyperstructure equipartition with a connected constraint, Solving graph coloring problems with the Douglas-Rachford algorithm, A nice class for the vertex packing problem, Variable and term removal from Boolean formulae, Triangulating planar graphs while minimizing the maximum degree, Graph bisection revisited, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, Discrete convexity in joint winner property, Pareto optimal matchings of students to courses in the presence of prerequisites, A method of graph reduction and its applications, The Metropolis algorithm for graph bisection, On polynomial kernelization of $\mathcal H$-\textsc{free edge deletion}, A coloring algorithm for $4 K_1$-free line graphs, A sufficient condition for planar graphs to be 3-colorable, Spectral methods for graph bisection problems., Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs, Computational aspects of greedy partitioning of graphs, Subcolorings and the subchromatic number of a graph, An augmenting graph approach to the stable set problem in $P_{5}$-free graphs, $P_{5}$-free augmenting graphs and the maximum stable set problem, Three colorability characterized by shrinking of locally connected subgraphs into triangles, Computational complexity aspects of point visibility graphs, Cardinality constrained minimum cut problems: complexity and algorithms., On contact graphs of paths on a grid, The stable roommates problem with short lists, Efficient heuristic algorithm for identifying critical nodes in planar networks, Complexity and algorithms for the connected vertex cover problem in 4-regular graphs, Finding a potential community in networks, $K$-adaptability in stochastic combinatorial optimization under objective uncertainty, A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs, Local search inequalities, Stable marriage and roommates problems with restricted edges: complexity and approximability, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, Projection results for the $k$-partition problem, A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem, Operads of finite posets, On the minimum size of an identifying code over all orientations of a graph, Saving colors and max coloring: some fixed-parameter tractability results, A discrete dynamic convexized method for the max-cut problem, The bandwidth sum of join and composition of graphs, Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances, Consistency in networks of relations, Approximation and dependence via multiteam semantics, Vertex deletion problems on chordal graphs, One more polynomial complete consecutive retrieval problem, The densest hemisphere problem, Hamilton cycles in hypergraphs below the Dirac threshold, On the complexity of some two-person perfect-information games, An intermediate-value theorem for optimum tree valuation, On approximation algorithms for concave mixed-integer quadratic programming, The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two, A priori TSP in the scenario model, The allocation problem in hardware design, On complexity of subset interconnection designs, On the communication complexity of zero-knowledge proofs, Parameterized complexity of vertex colouring, On cutting a few vertices from a graph, The use of dynamic programming in genetic algorithms for permutation problems, A unified approximation algorithm for node-deletion problems, Jump number maximization for proper interval graphs and series-parallel graphs, Three-quarter approximation for the number of unused colors in graph coloring, ``Global graph problems tend to be intractable, A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis, Computing the dimension of N-free ordered sets is NP-complete, The complexity of some problems related to GRAPH 3-COLORABILITY, Quantum stochastic optimization, An algorithm for colouring perfect planar graphs, On the algorithmic complexity of twelve covering and independence parameters of graphs, NP-completeness of a family of graph-colouring problems, The closure of monadic NP, Algorithms for graph partitioning problems by means of eigenspace relaxations, A linear algorithm for the domination number of a series-parallel graph, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, Optimal cutting directions and rectangle orientation algorithm, The line index and minimum cut of weighted graphs, Stable sets in certain $P_6$-free graphs, Maximum cut on line and total graphs, Which crossing number is it anyway?, The partial constraint satisfaction problem: Facets and lifting theorems, The domatic number problem on some perfect graph families, The computational complexity of knot and matroid polynomials, The NP-completeness of (1,r)-subcolorability of cubic graphs, Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications, Optimal scheduling in film production to minimize talent hold cost, Quadratic functions with exponential number of local maxima, Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems, Implications of forbidden structures for extremal algorithmic problems, CPG graphs: some structural and hardness results, Graph theoretic closure properties of the family of boundary NLC graph languages, Connected max cut is polynomial for graphs without the excluded minor $K_5\backslash e$, Balanced connected graph partition, Parameterizing role coloring on forests, On gallery watchmen in grids, The bipartite margin shop and maximum red matchings free of blue-red alternating cycles, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Constraint satisfaction with bounded treewidth revisited, On the complexity of the maximum satisfiability problem for Horn formulas, An efficient algorithm for solving pseudo clique enumeration problem, Upper bounds on the bisection width of 3- and 4-regular graphs, A parallel algorithm for bisection width in trees, Probabilistic satisfiability, The complexity of optimization problems, More complicated questions about maxima and minima, and some closures of NP, A polynomial characterization of some graph partitioning problems, The complexity of multicolouring, Optimal product design using conjoint analysis: Computational complexity and algorithms, A randomised 3-colouring algorithm, A hierarchy of propositional Horn formuls, The complexity of matching with bonds, On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three, An NC algorithm for Brooks' theorem, Testing the universal instance assumption, Interval scheduling and colorful independent sets, Data encodings and their costs, The node-deletion problem for hereditary properties is NP-complete, On finding minimal length superstrings, A semidefinite optimization approach to the target visitation problem, Are there any good digraph width measures?, Complexity of dimension three and some related edge-covering characteristics of graphs, On the complexity of computing bilinear forms with $\{0,1\}$ constants, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Optimization problems and the polynomial hierarchy, Discrete extremal problems, The complexity of a multiprocessor task assignment problem without deadlines, Balancing signed graphs, Routing with critical paths, Optimization and approximation algorithm for placement of records on linear storage devices, Complexity of representation of graphs by set systems, An efficient algorithm for edge coloring planar graphs with $\Delta$ colors, Methods for the one-dimensional space allocation problem, Coloring certain proximity graphs, Probabilistic bounds and algorithms for the maximum satisfiability problem, The splittance of a graph, NP-completeness of some generalizations of the maximum matching problem, Planar kernel and Grundy with $d\leq 3$, $dout\leq 2$, $din\leq 2$ are NP- complete, Unit disk graphs, On minimum dominating sets with minimum intersection, Why not negation by fixpoint?, Linear choosability of graphs, Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time, $\alpha$-vertex separator is NP-hard even for 3-regular graphs, Computing independent sets in graphs with large girth, A discrete filled function algorithm for approximate global solutions of max-cut problems, Expressing combinatorial optimization problems by linear programs, Reduction of indefinite quadratic programs to bilinear programs, Partition into cliques for cubic graphs: Planar case, complexity and approximation, On complexity of special maximum matchings constructing, A linear time algorithm for graph partition problems, Finding good approximate vertex and edge partitions is NP-hard, Max-cut in circulant graphs, Optimal cuts in graphs and statistical mechanics, Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem, The NP-completeness of the bandwidth minimization problem, Boolesche Minimalpolynome und Überdeckungsprobleme, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Parameterized algorithmics for linear arrangement problems, Complexity of conditional colorability of graphs, Bounds on isoperimetric values of trees, Cardinality constrained and multicriteria (multi)cut problems, On the complexity of finding balanced oneway cuts, Exact complexity of exact-four-colorability, Optimal one-page tree embeddings in linear time, A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems, Approximability of minimum AND-circuits, On star and caterpillar arboricity, The complexity of the $L(p,q)$-labeling problem for bipartite planar graphs of small degree, Vertex and edge covers with clustering properties: Complexity and algorithms, Parameterized complexity of finding regular induced subgraphs, Stable marriage with ties and bounded length preference lists, On the approximability of the maximum agreement subtree and maximum compatible tree problems, The submodular knapsack polytope, Vertex- and edge-minimal and locally minimal graphs, Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs, Partitioning graphs into complete and empty graphs, Planar graphs without adjacent cycles of length at most seven are 3-colorable, Efficient bounds for the stable set, vertex cover and set packing problems, Some undecidable problems involving the edge-coloring and vertex-coloring of graphs, Complete problems for space bounded subclasses of NP, Branch distance optimization of structured programs, An efficient parallel algorithm for computing a large independent set in a planar graph, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound, On the complexity of scheduling unit-time jobs with or-precedence constraints, Packing $r$-cliques in weighted chordal graphs, The longest common subsequence problem for sequences with nested arc annotations., A graph theoretical approach to the firebreak locating problem, Local base station assignment with time intervals in mobile computing environments, Star colouring of bounded degree graphs and regular graphs, On the existence of subexponential parameterized algorithms, On coloring a class of claw-free graphs., Vertex ordering and partitioning problems for random spatial graphs., On decision and optimization ($k$,$l$)-graph sandwich problems, Eulerian disjoint paths problem in grid graphs is NP-complete, Multistage vertex cover, Monge matrices make maximization manageable, Generating lower bounds for the linear arrangement problem, Hamiltonian problems in directed graphs with simple row patterns, The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix, Polynomial time algorithms for tracking path problems, On bandwidth and edgesum for the composition of two graphs, On computational capabilities of Ising machines based on nonlinear oscillators, Note on a conjecture of Toft, Computing the isoperimetric number of a graph, New results on independent sets in extensions of $2K_2$-free graphs, 1-extendability of independent sets, Partitions of graphs into one or two independent sets and cliques, List-coloring -- parameterizing from triviality, Tabu search for graph partitioning, Lower bounds for protrusion replacement by counting equivalence classes, Every planar graph without triangles adjacent to cycles of length 3 or 6 is $( 1 , 1 , 1 )$-colorable, Propositional truth maintenance systems: Classification and complexity analysis, On semidefinite programming relaxations of maximum $k$-section, Coloring Eulerian triangulations of the Klein bottle, Inapproximability of the Tutte polynomial of a planar graph, Exact solution of the 2-dimensional grid arrangement problem, Domination chain: characterisation, classical complexity, parameterised complexity and approximability, A step towards the strong version of Havel's three color conjecture, 3-colouring AT-free graphs in polynomial time, An exact algorithm for graph partitioning, A tighter upper bound for random MAX $2$-SAT, Complexity of determining the most vital elements for the $p$-median and $p$-center location problems, On the Grundy and $b$-chromatic numbers of a graph, Greed is good for deterministic scale-free networks, A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section, Fast 3-coloring triangle-free planar graphs, Linear and quadratic programming approaches for the general graph partitioning problem, Improved non-approximability results for minimum vertex cover with density constraints, Cuts in undirected graphs. I, An exact approach for the multi-constraint graph partitioning problem, Judicious partitions of 3-uniform hypergraphs, On the complexity of broadcast domination and multipacking In digraphs, Complexity of stability, Approximation and hardness of shift-Bribery, Parliament seating assignment problems, Partitioning to three matchings of given size is NP-complete for bipartite graphs, Stable-$\Pi$ partitions of graphs, An $O(n^4)$ time algorithm to compute the bisection width of solid grid graphs, Near-colorings: non-colorable graphs and NP-completeness, A graph partitioning strategy for solving large-scale crew scheduling problems, On partial Grundy coloring of bipartite graphs and chordal graphs, On some tractable and hard instances for partial incentives and target set selection, Chromatic number via Turán number, On minimum balanced bipartitions of triangle-free graphs, The complexity of the Hajós calculus for planar graphs, Two-stage stochastic matching and spanning tree problems: polynomial instances and approximation, Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph, Facility location problems: a parameterized view, The Chinese deliveryman problem, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Simultaneous node and link districting in transportation networks: model, algorithms and railway application, Complexity and algorithms for injective edge-coloring in graphs, A note on the fine-grained complexity of MIS on regular graphs, Scheduling parallel batching machines in a sequence, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs, Algorithmic aspects of upper edge domination, On the complexity of the smallest grammar problem over fixed alphabets, Coloring of pseudocubic graphs in three colors, Sliding window temporal graph coloring, A binarisation heuristic for non-convex quadratic programming with box constraints, On $t$-relaxed 2-distant circular coloring of graphs, New exact approaches to row layout problems, Independent sets in $(P_4+P_4$,triangle)-free graphs, Minimum fill-in: inapproximability and almost tight lower bounds, Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs, Minimum projective linearizations of trees in linear time, A complexity dichotomy for critical values of the $b$-chromatic number of graphs, Exact recovery in the Ising blockmodel, Voting on multi-issue domains with conditionally lexicographic preferences, A relaxation of Novosibirsk 3-color conjecture, Note on 3-choosability of planar graphs with maximum degree 4, Role coloring bipartite graphs, Computing the chromatic number using graph decompositions via matrix rank, On the maximum weight minimal separator, A survey on the problems and algorithms for covering arrays via set covers, Revising Johnson's table for the 21st century, Twin-width and polynomial kernels, Face covers and the genus problem for apex graphs, Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem., The complexity of quantum circuit mapping with fixed parameters, Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest, Towards a compact SAT-based encoding of itemset mining tasks, Placing Green bridges optimally, with a multivariate analysis, A refined branching algorithm for the maximum satisfiability problem, Efficient reassembling of graphs. I: The linear case, On the vertex packing problem, A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access, Tutte sets in graphs. II: The complexity of finding maximum Tutte sets, On finding Min-Min disjoint paths, Reconfiguration of colorable sets in classes of perfect graphs, Unnamed Item, Polynomial algorithms for protein similarity search for restricted mRNA structures, On the kernelization of split graph problems, On 3-chromatic distance-regular graphs, Graph separation techniques for quadratic zero-one programming, Some observations on maximum weight stable sets in certain $P_{5}$-free graphs, Isoperimetric numbers of graphs, Configuration of airspace sectors for balancing air traffic controller workload, Unnamed Item, A note on the concrete hardness of the shortest independent vector in lattices, A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs, The control complexity of $r$-Approval: from the single-peaked case to the general case, On the balanceability of some graph classes, Monopolar graphs: complexity of computing classical graph parameters, Simultaneous feedback edge set: a parameterized perspective, 4-coloring $(P_6, \text{bull})$-free graphs, Kernelization and approximation of distance-$r$ independent sets on nowhere dense graphs, New upper bounds for the chromatic number of a graph, Vertex Cover Reconfiguration and Beyond, The pairwise flowtime network construction problem, Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations, Generalised 2-circulant inequalities for the max-cut problem, Homomorphism bounds of signed bipartite $K_4$-minor-free graphs and edge-colorings of $2k$-regular $K_4$-minor-free multigraphs, Equitable coloring of hypergraphs, The proper vertex-disconnection of graphs, A note on the 2-circulant inequalities for the MAX-cut problem, On the computational complexity of the bipartizing matching problem, On the complexity of restoring corrupted colorings, Gene tree reconciliation including transfers with replacement is NP-hard and FPT, The $r$-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size, Chordal bipartite completion of colored graphs, Approximation of the quadratic set covering problem, Phase transition of degeneracy in minor-closed families, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Maximum Weighted Independent Sets with a Budget, Distance-$d$ independent set problems for bipartite and chordal graphs, Card-based zero-knowledge proof protocols for graph problems and their computational model, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, A survey of graph coloring - its types, methods and applications, Boundary graph classes for some maximum induced subgraph problems, Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth, The vertex cover $P_3$ problem in cubic graphs, $d$-dimensional arrangement revisited, Strong edge-colouring and induced matchings, Solutions for the stable roommates problem with payments, A characterization of partial directed line graphs, A semidefinite programming approach to the hypergraph minimum bisection problem, The scaling window of the 2-SAT transition, CHECKCOL: improved local search for graph coloring, Dichotomy for Coloring of Dart Graphs, The Complexity Status of Problems Related to Sparsest Cuts, Stable sets of maximum weight in ($P_{7}$, banner)-free graphs, On the minimum load coloring problem, A new method, the fusion fission, for the relaxed $k$-way graph partitioning problem, and comparisons with some multilevel algorithms, Coloring graphs by iterated local search traversing feasible and infeasible solutions, A survey of metaheuristic-based techniques for university timetabling problems, Embedding a novel objective function in a two-phased local search for robust vertex coloring, Triangle-free subcubic graphs with minimum bipartite density, Unnamed Item, Unnamed Item, Unnamed Item, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Partition the vertices of a graph into one independent set and one acyclic set, NP-completeness results for edge modification problems, Finding optimal solutions to the graph partitioning problem with heuristic search, Maximum incomplete recursive circulants in graph embeddings, The partial inverse minimum cut problem withL₁-norm is strongly NP-hard, Measuring Indifference: Unit Interval Vertex Deletion, On the Grundy Number of a Graph, The role of planarity in connectivity problems parameterized by treewidth, SDP Relaxations for Some Combinatorial Optimization Problems, Unbalanced graph cuts with minimum capacity, Maximum algebraic connectivity augmentation is NP-hard, Edge vulnerability parameters of bisplit graphs, On the Hardness of Switching to a Small Number of Edges, Open Problems on Graph Coloring for Special Graph Classes, On the Complexity of Computing the k-restricted Edge-connectivity of a Graph, A Reconfigurations Analogue of Brooks' Theorem and Its Consequences, Orthogonal representations over finite fields and the chromatic number of graphs, Partitioning cographs into cliques and stable sets, Bisplit graphs, The complexity of solution-free sets of integers for general linear equations, On chromatic number and minimum cut, From edge-coloring to strong edge-coloring, On qualitative route descriptions. Representation, agent models, and computational complexity, Separator-based graph embedding into multidimensional grids with small edge-congestion, Obtaining matrices with the consecutive ones property by row deletions, Incompressibility of $H$-free edge modification problems, Connected surveillance game, The maximum independent set problem in subclasses of subcubic graphs, Combinatorial voter control in elections, Semidefinite programming and eigenvalue bounds for the graph partition problem, MINING POSETS FROM LINEAR ORDERS, Global optimization of nonconvex problems with multilinear intermediates, 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, The Complexity of Coloring Circular Arcs and Chords, An algorithm for the maximum internally stable set in a weighted graph, Polynomial Time Algorithms for Tracking Path Problems, Altruistic Hedonic Games, On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphs, Complexity and Polynomially Solvable Special Cases of QUBO, The Boolean Quadric Polytope, Further Algebraic Results in the Theory of Balance, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, On limitations of transformations between combinatorial problems, Minimum Linear Arrangement of Series-Parallel Graphs, Fast Distributed Approximation for Max-Cut, Iterative coloring extension of a maximum clique, On the complexity of approximating and illuminating three-dimensional convex polyhedra, On approximation properties of the Independent set problem for degree 3 graphs, A Dynamic Programming Algorithm To Test A Signed Graph For Balance, Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results, Coloration de graphes : fondements et applications, Unnamed Item, DP-Complete Problems Derived from Extremal NP-Complete Properties, A simulated annealing algorithm for allocating space to manufacturing cells, On coloring problems for two-season multigraphs, On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations, THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP, MAXIMUM INDEPENDENT, MINIMALLY REDUNDANT SETS IN SERIES-PARALLEL GRAPHS, Graph Bisection with Pareto Optimization, Graph layout problems, A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph, Monotone Crossing Number, Inductive graph invariants and approximation algorithms, On the computational complexity of ordered subgraph recognition, Γ-limit of the cut functional on dense graph sequences, Approximation Algorithms for Geometric Intersection Graphs, The bisection width of grid graphs, Unnamed Item, Finding a Hamilton cycle fast on average using rotations and extensions, A variation on the min cut linear arrangement problem, Fractals for Kernelization Lower Bounds, A survey on Mesh Segmentation Techniques, Dynamic Balanced Graph Partitioning, Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth, The approximation of maximum subgraph problems, On circular layouts^∗, On Computational Aspects of Greedy Partitioning of Graphs, On the hardness of range assignment problems, Why Is Maximum Clique Often Easy in Practice?, A guide to conic optimisation and its applications, On the computational complexity of centers locating in a graph, Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs, Computing the Chromatic Number Using Graph Decompositions via Matrix Rank, Randomized Greedy Algorithms for Independent Sets and Matchings in Regular Graphs: Exact Results and Finite Girth Corrections, Coloring graphs with fixed genus and girth, Isoperimetry in integer lattices, Crossing Number is NP-Complete, Unnamed Item, A Complexity Dichotomy for the Coloring of Sparse Graphs, Balanced paths in acyclic networks: Tractable cases and related approaches, Channel assignment and weighted coloring, A Note on k-Colorability of P 5-Free Graphs, The adjacency relation on the traveling salesman polytope is NP-Complete, Unnamed Item, Unnamed Item, Approximate algorithms for generalized maximum utility problems, On triangulating planar graphs under the four-connectivity constraint, Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings, Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing, Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable, One-message statistical Zero-Knowledge Proofs and space-bounded verifier, Unnamed Item, On the computational complexity of the Jones and Tutte polynomials, Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling, NP-Complete operations research problems and approximation algorithms, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, Coloring Graphs with Constraints on Connectivity, Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity, On the Parameterised Intractability of Monadic Second-Order Logic, NP-completeness of some optimal sequencing problems with a given grouping of elements, A TWO-STATE ANT COLONY ALGORITHM FOR SOLVING THE MINIMUM GRAPH BISECTION PROBLEM, Optimal Numberings of an $N \times N$ Array, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, On BMRN*-colouring of planar digraphs, On the Independence Number of Graphs with Maximum Degree 3, The complexity of the matching-cut problem for planar graphs and other graph classes, Recognizing Graphs Close to Bipartite Graphs, The Complexity of the Partial Order Dimension Problem, On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance, Reconfiguration of Colorable Sets in Classes of Perfect Graphs, Packing of (0, 1)-matrices, Computing the norm ∥A∥∞,1 is NP-hard^∗, Unnamed Item, Unnamed Item, On the Cutwidth and the Topological Bandwidth of a Tree, Subdivision of the hierarchy of H-colorable graph classes by circulant graphs, Characterizing –partitionable Cographs, Vertex Deletion Problems on Chordal Graphs, Hill Climbing with Multiple Local Optima, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs, Locally finite properties of data structures and their computation, Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time, Computing the Minimum Fill-In is NP-Complete, Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs, The power of two choices for random walks, On the Complexity of Finding a Potential Community, Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs, On the Hardness and Approximability of Planar Biconnectivity Augmentation, On the computational complexity of Roman$\{2\}$-domination in grid graphs, MaxCut on permutation graphs is NP‐complete, Minimum weighted clique cover on claw‐free perfect graphs, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, Independent set under a change constraint from an initial solution, The maximum linear arrangement problem for trees under projectivity and planarity, The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number, The notion of abstraction in ontology-based data management, Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$, Sudoku number of graphs, Optimizing concurrency under Scheduling by Edge Reversal, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Equitable scheduling on a single machine, Computing dense and sparse subgraphs of weakly closed graphs, Partitioning through projections: strong SDP bounds for large graph partition problems, Revisiting maximum satisfiability and related problems in data streams, Row Replicated Block Cimmino, Phragmén's voting methods and justified representation, Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes, Maximum cut on interval graphs of interval count four is NP-complete, New results on the robust coloring problem, Color-avoiding connected spanning subgraphs with minimum number of edges, Exact enumeration of satisfiable 2-SAT formulae, 3-coloring $C_4$ or $C_3$-free diameter two graphs, The max-out min-in problem: a tool for data analysis, An approximation algorithm for indefinite mixed integer quadratic programming, The board packing problem, Revisiting maximum satisfiability and related problems in data streams, Computing maximum matchings in temporal graphs, A note on Hamiltonian cycles in planar graphs, On the complexity of binary polynomial optimization over acyclic hypergraphs, Algorithmic theory of qubit routing, Connected graph partitioning with aggregated and non‐aggregated gap objective functions, New approximation results on graph matching and related problems, Improved non-approximability results for vertex cover with density constraints, Efficient game theoretic approach to dynamic graph partitioning, Covering a Graph with Clubs, Between 2- and 3-colorability, The complexity of linear programming, How to divide a catchment to conquer its parallel processing. An efficient algorithm for the partitioning of water catchments, 1-extendability of independent sets, Complexity classification of some edge modification problems, Optimal arrangement of data in a tree directory, The edge-disjoint paths problem is NP-complete for series-parallel graphs, Scheduling with forbidden sets, A branch and bound method for solving the bidirectional circular layout problem, Approximating the minimum hub cover problem on planar graphs, The computational complexity of the pooling problem, NP-completeness results for partitioning a graph into total dominating sets, On cycle transversals and their connected variants in the absence of a small linear forest, Complexity of fall coloring for restricted graph classes, Fixed-parameter tractability of $(n-k)$ list coloring, Experiments on the minimum linear arrangement problem, Maximum cuts in edge-colored graphs, Lower bounds for the happy coloring problems, Parameterized inapproximability of independent set in $H$-free graphs, On the tractability of covering a graph with 2-clubs, Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations, Unnamed Item, Unnamed Item, Some of My Favorite Coloring Problems for Graphs and Digraphs, Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs, Communication Avoiding ILU0 Preconditioner, Selected Topics in Critical Element Detection, Complexity of the weighted max-cut in Euclidean space

Cites Work