Perfect zero–one matrices

DOI10.1007/BF01580235zbMath0284.90061MaRDI QIDQ4770779

Publication date: 1974

Published in: Mathematical Programming (Search for Journal in Brave)

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10) Positive matrices and their generalizations; cones of matrices (15B48)

Related Items

Elementary bipartite graphs and unique colourability, On the Chvátal-rank of Antiwebs, Near-perfect matrices, New classes of Berge perfect graphs, A note on clutter partitions, Perfect graphs with no $P_ 5$ and no $K_ 5$, Slightly triangulated graphs are perfect, An extension of Lehman's theorem and ideal set functions, Lift-and-project ranks of the stable set polytope of joined $a$-perfect graphs, A reduction procedure for coloring perfect $K_ 4$-free graphs, Generalized perfect graphs: Characterizations and inversion, On the integer properties of scheduling set partitioning models, Order preserving assignments without contiguity, On transversals in minimal imperfect graphs, Perfect graphs with unique $P_ 4$-structure, A min-max relation for $K_ 3$-covers in graphs noncontractible to $K_ 5\backslash e$, A construction for non-rank facets of stable set polytopes of webs, Directed Moore hypergraphs, Locally perfect graphs, No antitwins in minimal imperfect graphs, Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes, Wings and perfect graphs, Chair-free Berge graphs are perfect, On a conjecture about uniquely colorable perfect graphs, On essential components and critical sets of a graph, On perfect graphs and polyhedra with (0, 1)-valued extreme points, Applying Lehman's theorems to packing problems, Computing clique and chromatic number of circular-perfect graphs in polynomial time, Perfect graphs are kernel solvable, Some properties of minimal imperfect graphs, Minimal imperfect graphs: A simple approach, Graphical properties related to minimal imperfection, Complementation in T-perfect graphs, A Class of Balanced Matrices Arising from Location Problems, A Sum of Squares Characterization of Perfect Graphs, A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties, Alternatives for testing total dual integrality, Discrete extremal problems, Perfect graphs, kernels, and cores of cooperative games, Grinstead's conjecture is true for graphs with a small clique number, A Berge-keeping operation for graphs, An approach to solving $A^{k}=J-I$, The strong perfect graph conjecture for toroidal graphs, A classification of certain graphs with minimal imperfection properties, Cayley partitionable graphs and near-factorizations of finite groups, On stable set polyhedra for K//(1,3)free graphs, Meyniel graphs are strongly perfect, On circular-perfect graphs: a survey, On circulant thin Lehman matrices, Forced color classes, intersection graphs and the strong perfect graph conjecture, Perfect $(0,\pm 1)$-matrices and perfect bidirected graphs, Perfect $0,\pm 1$ matrices, Properties of balanced and perfect matrices, Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets, On the mixed set covering, packing and partitioning polytope, Lehman's forbidden minor characterization of ideal 0-1 matrices, On a graph partition problem with application to VLSI layout, Testing balancedness and perfection of linear matrices, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, On classes of minimal circular-imperfect graphs, On the strong perfect graph conjecture, A class of polynomially solvable 0-1 programming problems and an application, On non-rank facets of stable set polytopes of webs with clique number four, A class of facet producing graphs for vertex packing polyhedra, Perfect, ideal and balanced matrices, On $f$-domination: polyhedral and algorithmic results, A note on the total unimodularity of matrices, On a connection between facility location and perfect graphs, Almost integral polyhedra related to certain combinatorial optimization problems, Efficient solutions for special zero-one programming problems, Classification de certaines matrices 0-1, Critical perfect graphs and perfect 3-chromatic graphs, The stable set polytope for some extensions of $P_4$-free graphs, Local unimodularity of matrix-vector pairs, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, Combinatorial designs related to the strong perfect graph conjecture, Thin Lehman matrices arising from finite groups, Odd cycles and matrices with integrality properties, Unnamed Item, Structure of cubic Lehman matrices, Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, Uniquely colorable perfect graphs, On minimal imperfect graphs without induced $P_5$, $P_4$-domination in minimal imperfect graphs, The strong perfect graph conjecture: 40 years of attempts, and its resolution, An iterative approach to robust and integrated aircraft routing and crew scheduling, The train driver recovery problem-a set partitioning based model and solution method, About skew partitions in minimal imperfect graphs, On circular critical graphs, A family of perfect graphs associated with directed graphs, Almost all webs are not rank-perfect, Polynomially bounded algorithms for locatingp-centers on a tree, On cliques associated to 3-set packing problems, On determining the imperfection ratio, On the Laplacian spectrum of ($\alpha,\omega$)-graphs

Cites Work