scientific article; zbMATH DE number 3882470

zbMATH Open0554.05041MaRDI QIDQ3216686FDOQ3216686

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

Publication date: 1984

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 3908479
• Progress on perfect graphs
• Computing the clique number of \(a\)-perfect graphs in polynomial time
• scientific article; zbMATH DE number 3893237
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs

zbMATH Keywords

linear programmingpolynomial methodpolynomial algorithmsperfect graphsmaximal cliqueellipsoid methodmaximal stable setmaximum weighted cliqueminimal coloringmaximum weighted stable subsetminimal clique cover

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• Polynomial and APX-hard cases of the individual haplotyping problem
• On the parameterized complexity of coloring graphs in the absence of a linear forest
• Recognizing Graphs Close to Bipartite Graphs
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• Transitive orientations in bull-reducible Berge graphs
• The maximum clique problem
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Colouring vertices of triangle-free graphs without forests
• Graphs without large apples and the maximum weight independent set problem
• Independent packings in structured graphs
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Proper interval vertex deletion
• Clustering and domination in perfect graphs
• On the use of Boolean methods for the computation of the stability number
• The complexity of dissociation set problems in graphs
• Orthogonal representations and connectivity of graphs
• Title not available (Why is that?)
• On the stable set problem in special \(P_{5}\)-free graphs
• Convexity in partial cubes: the hull number
• Completely separable graphs
• Title not available (Why is that?)
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Independent feedback vertex sets for graphs of bounded diameter
• Polynomially solvable cases for the maximum stable set problem
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Optimizing weakly triangulated graphs
• New results on independent sets in extensions of \(2K_2\)-free graphs
• \(F\)-WORM colorings: results for 2-connected graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Recognition of unipolar and generalised split graphs
• Comparability graph augmentation for some multiprocessor scheduling problems
• List coloring in the absence of a linear forest
• The theta body and imperfection
• Relaxations of vertex packing
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Clique and chromatic number of circular-perfect graphs
• A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
• Solving some NP-complete problems using split decomposition
• Open problems on graph coloring for special graph classes
• On edge perfectness and classes of bipartite graphs
• Regular inference as vertex coloring
• Stability number of bull- and chair-free graphs
• On the complexity of the independent set problem in triangle graphs
• Coloring graphs characterized by a forbidden subgraph
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Well-covered graphs and extendability
• The 0-1 inverse maximum stable set problem
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Independent sets in asteroidal triple-free graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• Complexity of coloring graphs without paths and cycles
• Colouring perfect graphs with bounded clique number
• Testing membership in matroid polyhedra
• Optimal channel allocation for several types of cellular radio networks
• 4-coloring \(H\)-free graphs when \(H\) is small
• An algorithm for finding a maximum clique in a graph
• An algorithm for finding homogeneous pairs
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Restricted coloring models for timetabling
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Some geometric results in semidefinite programming
• On the structure of bull-free perfect graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• On bounding the difference of the maximum degree and the clique number
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring
• On the structure of graphs without claw, \(4K_1\) and co-R
• Matching colored points with rectangles
• Independent set of intersection graphs of convex objects in 2D
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Computing clique and chromatic number of circular-perfect graphs in polynomial time
• The perfection and recognition of bull-reducible Berge graphs
• Perfect graphs and guarding rectilinear art galleries
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Minimum cost and list homomorphisms to semicomplete digraphs
• Testing consumer rationality using perfect graphs and oriented discs
• Faster 3-coloring of small-diameter graphs
• Title not available (Why is that?)
• Mode packing and perfect graphs
• Lifting for simplicity: concise descriptions of convex sets
• Even pairs in claw-free perfect graphs
• Colouring square-free graphs without long induced paths
• A reduction procedure for coloring perfect \(K_ 4\)-free graphs
• Colouring Some Classes of Perfect Graphs Robustly
• Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem
• Title not available (Why is that?)
• Polyhedral sets and integer rounding
• Perfect circular arc coloring
• On dart-free perfectly contractile graphs
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• Path parity and perfection

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3216686)