Perfect zero–one matrices
From MaRDI portal
Publication:4770779
DOI10.1007/BF01580235zbMATH Open0284.90061MaRDI QIDQ4770779FDOQ4770779
Authors: Manfred Padberg 
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)
Cites Work
- Normal hypergraphs and the perfect graph conjecture
- On certain polytopes associated with graphs
- A characterization of perfect graphs
- On the facial structure of set packing polyhedra
- Blocking and anti-blocking pairs of polyhedra
- On the Set-Covering Problem
- Balanced matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (97)
- Graphical properties related to minimal imperfection
- Almost all webs are not rank-perfect
- Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture
- Testing balancedness and perfection of linear matrices
- Perfect, ideal and balanced matrices
- A reduction procedure for coloring perfect \(K_ 4\)-free graphs
- No antitwins in minimal imperfect graphs
- On circular critical graphs
- An approach to solving \(A^{k}=J-I\)
- A class of polynomially solvable 0-1 programming problems and an application
- Locally perfect graphs
- Wings and perfect graphs
- Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets
- Properties of balanced and perfect matrices
- Perfect graphs are kernel solvable
- Lehman's forbidden minor characterization of ideal 0-1 matrices
- A note on the total unimodularity of matrices
- Local unimodularity of matrix-vector pairs
- Combinatorial designs related to the strong perfect graph conjecture
- Efficient solutions for special zero-one programming problems
- Near-perfect matrices
- A class of facet producing graphs for vertex packing polyhedra
- Odd cycles and matrices with integrality properties
- Critical perfect graphs and perfect 3-chromatic graphs
- Generalized perfect graphs: Characterizations and inversion
- An extension of Lehman's theorem and ideal set functions
- Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs
- On classes of minimal circular-imperfect graphs
- On \(f\)-domination: polyhedral and algorithmic results
- Chair-free Berge graphs are perfect
- Discrete extremal problems
- Grinstead's conjecture is true for graphs with a small clique number
- The stable set polytope for some extensions of \(P_4\)-free graphs
- A construction for non-rank facets of stable set polytopes of webs
- A classification of certain graphs with minimal imperfection properties
- On stable set polyhedra for K//(1,3)free graphs
- Polynomially bounded algorithms for locatingp-centers on a tree
- New classes of Berge perfect graphs
- On a graph partition problem with application to VLSI layout
- Almost integral polyhedra related to certain combinatorial optimization problems
- Perfect graphs, kernels, and cores of cooperative games
- A Class of Balanced Matrices Arising from Location Problems
- On circular-perfect graphs: a survey
- On non-rank facets of stable set polytopes of webs with clique number four
- On the strong perfect graph conjecture
- Applying Lehman's theorems to packing problems
- On circulant thin Lehman matrices
- On a conjecture about uniquely colorable perfect 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
- Thin Lehman matrices arising from finite groups
- On the integer properties of scheduling set partitioning models
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- On the Laplacian spectrum of (\(\alpha,\omega\))-graphs
- Some properties of minimal imperfect graphs
- Claw-free \(t\)-perfect graphs can be recognized in polynomial time
- A family of perfect graphs associated with directed graphs
- Uniquely colorable perfect graphs
- Computing clique and chromatic number of circular-perfect graphs in polynomial time
- Minimal imperfect graphs: A simple approach
- The strong perfect graph conjecture for toroidal graphs
- Alternatives for testing total dual integrality
- Meyniel graphs are strongly perfect
- About skew partitions in minimal imperfect graphs
- Perfect \(0,\pm 1\) matrices
- A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
- On cliques associated to 3-set packing problems
- Structure of cubic Lehman matrices
- Classification de certaines matrices 0-1
- Elementary bipartite graphs and unique colourability
- On the Chvàtal-rank of antiwebs
- A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties
- Cayley partitionable graphs and near-factorizations of finite groups
- The robust chromatic number of graphs
- A Sum of Squares Characterization of Perfect Graphs
- The strength of Dantzig-Wolfe reformulations for the stable set and related problems
- On the mixed set covering, packing and partitioning polytope
- Directed Moore hypergraphs
- \(P_4\)-domination in minimal imperfect graphs
- On minimal imperfect graphs without induced \(P_5\)
- Title not available (Why is that?)
- On a connection between facility location and perfect graphs
- Reverse lexicographic squarefree initial ideals and Gorenstein Fano polytopes
- A note on clutter partitions
- Complementation in T-perfect graphs
- Slightly triangulated graphs are perfect
- A Berge-keeping operation for graphs
- Order preserving assignments without contiguity
- On transversals in minimal imperfect graphs
- Perfect graphs with unique \(P_ 4\)-structure
- On determining the imperfection ratio
- On perfect graphs and polyhedra with (0, 1)-valued extreme points
- On essential components and critical sets of a graph
- The optimal cost chromatic partition problem for trees and interval graphs
- Forced color classes, intersection graphs and the strong perfect graph conjecture
- Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs
This page was built for publication: Perfect zero–one matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4770779)
