Publication:3216686
From MaRDI portal
zbMath0554.05041MaRDI QIDQ3216686
Alexander Schrijver, László Lovász, Martin Grötschel
Publication date: 1984
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
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
05C15: Coloring of graphs and hypergraphs
Related Items
The perfection and recognition of bull-reducible Berge graphs, Comparability graph augmentation for some multiprocessor scheduling problems, An algorithm for finding homogeneous pairs, On the structure of bull-free perfect graphs, Even pairs in claw-free perfect graphs, A note on line digraphs and the directed max-cut problem, Stability number of bull- and chair-free graphs, An algorithm for finding a maximum clique in a graph, 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, On Tucker vertices of graphs, The maximum clique problem, Well-covered graphs and extendability, Perfect graphs with no \(P_ 5\) and no \(K_ 5\), Geometric comparison of combinatorial polytopes, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, 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, A nice class for the vertex packing problem, On the use of Boolean methods for the computation of the stability number, Optimal channel allocation for several types of cellular radio networks, 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, On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs, An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs, Stability in \(P_5\)- and banner-free graphs, NeST graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, Polynomial and APX-hard cases of the individual haplotyping problem, On the stable set problem in special \(P_{5}\)-free graphs, Gridline graphs: A review in two dimensions and an extension to higher dimensions, Independent sets of maximum weight in (\(p,q\))-colorable graphs., On dart-free perfectly contractile graphs, Polynomially solvable cases for the maximum stable set problem, Generalized perfect graphs: Characterizations and inversion, Some geometric results in semidefinite programming, On edge perfectness and classes of bipartite graphs, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Perfect circular arc coloring, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Independent packings in structured graphs
