scientific article

László Lovász, Martin Grötschel, Alexander Schrijver

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

linear programming perfect graphs polynomial algorithms maximal stable set maximal clique polynomial method ellipsoid method maximum weighted clique minimal coloring maximum weighted stable subset minimal clique cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items

Quadratic bottleneck knapsack problems, Clique and chromatic number of circular-perfect graphs, One-three join: a graph operation and its consequences, 4-Coloring H-Free Graphs When H Is Small, Lifting for Simplicity: Concise Descriptions of Convex Sets, Complexity and Polynomially Solvable Special Cases of QUBO, The story of perfectly orderable graphs, Jin Akiyama: a friend and his mathematics (on the occasion of his 60th birthday), On box totally dual integral polyhedra, A Scheme for Computing Minimum Covers within Simple Regions, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, A linear kernel for finding square roots of almost planar graphs, Colouring diamond-free graphs, $F$-WORM colorings: results for 2-connected graphs, Independent sets in asteroidal triple-free graphs, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Colouring square-free graphs without long induced paths., Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, A refinement on the structure of vertex-critical $(P_5, \mathrm{gem})$-free graphs, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, Clique‐width: Harnessing the power of atoms, An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†, Induced odd cycle packing number, independent sets, and chromatic number, An optimal χ‐bound for (P6, diamond)‐free graphs, The clique problem with multiple-choice constraints under a cycle-free dependency graph, Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model, Complexity results on cosecure domination in graphs, Stable commutator length in right‐angled Artin and Coxeter groups, Maximizing the strong triadic closure in split graphs and proper interval graphs, A scheme for computing minimum covers within simple regions, Vertex-critical $( P_3 + \ell P_1 )$-free and vertex-critical (gem, co-gem)-free graphs, Perfect graphs and guarding rectilinear art galleries, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, An SDP primal-dual algorithm for approximating the Lovász-theta function, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, List coloring in the absence of a linear forest, Independent set of intersection graphs of convex objects in 2D, Unnamed Item, Minimum cost and list homomorphisms to semicomplete digraphs, The perfection and recognition of bull-reducible Berge graphs, On the complexity of the independent set problem in triangle graphs, The complexity of dissociation set problems in graphs, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Computing the clique number of $a$-perfect graphs in polynomial time, Comparability graph augmentation for some multiprocessor scheduling problems, On 3-coloring of $(2P_4,C_5)$-free graphs, Extended formulations from communication protocols in output-efficient time, On 3-coloring of $(2P_4,C_5)$-free graphs, The intersection of two vertex coloring problems, Colouring H-free graphs of bounded diameter., Open Problems on Graph Coloring for Special Graph Classes, Unnamed Item, List Coloring in the Absence of a Linear Forest, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, Colouring square-free graphs without long induced paths, Recognizing Graphs Close to Bipartite Graphs, Miscellaneous Digraph Classes, Perfect circular arc coloring, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Independent packings in structured graphs, Colouring Some Classes of Perfect Graphs Robustly, Faster 3-Coloring of Small-Diameter Graphs, NeST graphs, Independent sets of maximum weight in ($p,q$)-colorable graphs., Relaxations of vertex packing, Vertex coloring $(4K_1$, hole-twin, 5-wheel)-free graphs, Perfect graphs with no $P_ 5$ and no $K_ 5$, On coloring a class of claw-free graphs., Geometric comparison of combinatorial polytopes, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, On dart-free perfectly contractile graphs, A reduction procedure for coloring perfect $K_ 4$-free graphs, Polynomially solvable cases for the maximum stable set problem, Generalized perfect graphs: Characterizations and inversion, Deciding $k$-colorability of $P_5$-free graphs in polynomial time, Coloring perfect degenerate graphs, Restricted coloring models for timetabling, Path parity and perfection, On semi-$P_ 4$-sparse graphs, On the optimal transversals of the odd cycles, Some geometric results in semidefinite programming, A nice class for the vertex packing problem, On the use of Boolean methods for the computation of the stability number, On the structure of graphs without claw, $4K_1$ and co-R, Complexity of coloring graphs without paths and cycles, A sufficient condition to extend polynomial results for the maximum independent set problem, New results on independent sets in extensions of $2K_2$-free graphs, Novel evolutionary models and applications to sequence alignment problems, On edge perfectness and classes of bipartite graphs, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Optimal channel allocation for several types of cellular radio networks, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Computing clique and chromatic number of circular-perfect graphs in polynomial time, Weighted parameters in $(P_5,\overline {P_5})$-free graphs, An algorithm for coloring some perfect graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Even pairs in claw-free perfect graphs, Colouring $(P_r + P_s)$-free graphs, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, On extended $P_4$-reducible and extended $P_4$-sparse graphs, Independent feedback vertex sets for graphs of bounded diameter, A coloring algorithm for $4 K_1$-free line graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, Some problems on induced subgraphs, Convexity in partial cubes: the hull number, Partially concurrent open shop scheduling with integral preemptions, Proper interval vertex deletion, An augmenting graph approach to the stable set problem in $P_{5}$-free graphs, On colouring $(2P_2,H)$-free and $(P_5,H)$-free graphs, On the parameterized complexity of coloring graphs in the absence of a linear forest, Regular inference as vertex coloring, Spectral bounds for the independence ratio and the chromatic number of an operator, A note on line digraphs and the directed max-cut problem, Coloring graphs characterized by a forbidden subgraph, Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem, Shuffling biological sequences with motif constraints, Polynomial cases for the vertex coloring problem, Recognition of unipolar and generalised split graphs, Perfect $(0,\pm 1)$-matrices and perfect bidirected graphs, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, On bounding the difference of the maximum degree and the clique number, Improved complexity results on $k$-coloring $P_t$-free graphs, An algorithm for finding homogeneous pairs, On the structure of bull-free perfect graphs, Two complexity results for the vertex coloring problem, Solving some NP-complete problems using split decomposition, Matching colored points with rectangles, The 0-1 inverse maximum stable set problem, Maximum regular induced subgraphs in $2P_3$-free graphs, Transitive orientations in bull-reducible Berge graphs, Stability number of bull- and chair-free graphs, Independent sets in extensions of 2$K_{2}$-free graphs, Polynomial and APX-hard cases of the individual haplotyping problem, Contraction and deletion blockers for perfect graphs and $H$-free graphs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Graphs without large apples and the maximum weight independent set problem, Independent sets in $(P_4+P_4$,triangle)-free graphs, An algorithm for finding a maximum clique in a graph, Coloring Artemis graphs, On list $k$-coloring convex bipartite graphs, Packing paths perfectly, Optimizing weakly triangulated graphs, Orthogonal representations and connectivity of graphs, Colouring vertices of triangle-free graphs without forests, Weighted sum coloring in batch scheduling of conflicting jobs, The complexity of some problems related to GRAPH 3-COLORABILITY, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, Sequential colorings and perfect graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Stability in $P_5$- and banner-free graphs, On coloring a class of claw-free and hole-twin-free graphs, On Tucker vertices of graphs, Testing membership in matroid polyhedra, On the stable set problem in special $P_{5}$-free graphs, Gridline graphs: A review in two dimensions and an extension to higher dimensions, Clustering and domination in perfect graphs, The maximum clique problem, Well-covered graphs and extendability, Algorithms and almost tight results for 3-colorability of small diameter graphs