Near-perfect matrices
From MaRDI portal
Publication:1332310
DOI10.1007/BF01582578zbMath0804.05036MaRDI QIDQ1332310
Publication date: 10 October 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
strong perfect graph conjectureimperfect graphsperfect matricesclique-node incidence matricesnear- perfect graphs
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (22)
Comparing Imperfection Ratio and Imperfection Index for Graph Classes ⋮ Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs ⋮ Unnamed Item ⋮ Applying Lehman's theorems to packing problems ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ The stable set polytope of icosahedral graphs ⋮ Characterizing N+-perfect line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ 2-clique-bond of stable set polyhedra ⋮ Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ On facets of stable set polytopes of claw-free graphs with stability number 3 ⋮ On non-rank facets of stable set polytopes of webs with clique number four ⋮ On a certain class of nonideal clutters ⋮ On packing and covering polyhedra of consecutive ones circulant clutters ⋮ On the set covering polyhedron of circulant matrices ⋮ Unnamed Item ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ Near-perfect graphs with polyhedral ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Generalized clique family inequalities for claw-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphical properties related to minimal imperfection
- The ellipsoid method and its consequences in combinatorial optimization
- Almost integral polyhedra related to certain combinatorial optimization problems
- Critical perfect graphs and perfect 3-chromatic graphs
- Combinatorial designs related to the strong perfect graph conjecture
- On certain polytopes associated with graphs
- A characterization of perfect graphs
- Normal hypergraphs and the perfect graph conjecture
- Integer Rounding for Polymatroid and Branching Optimization Problems
- Polyhedra for Composed Independence Systems
- Perfect zero–one matrices
- On the facial structure of set packing polyhedra
- On the strong perfect graph conjecture
This page was built for publication: Near-perfect matrices
