\(K_ i\)-covers. I: Complexity and polytopes
From MaRDI portal
Publication:1070249
DOI10.1016/0012-365X(86)90156-1zbMath0584.05052OpenAlexW1966227787MaRDI QIDQ1070249
Ali Ridha Mahjoub, Derek Gordon Corneil, Michele Conforti
Publication date: 1986
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(86)90156-1
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polytopes and polyhedra (52Bxx)
Related Items
Iterated \(k\)-line graphs, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\), Infinite \(\Phi\)-periodic graphs, A semidefinite approach to the $K_i$-cover problem, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, On the 0,1 facets of the set covering polytope, On the facial structure of the set covering polytope, Gallai graphs and anti-Gallai graphs, Triangle packings and transversals of some \(K_{4}\)-free graphs, Generalized line graphs: Cartesian products and complexity of recognition, On a composition of independence systems by circuit identification, The complexity of generalized clique covering, Composition of graphs and the triangle-free subgraph polytope
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on a conjecture by Gavril on clique separable graphs
- Polytope des independants d'un graphe série-parallèle
- Weakly bipartite graphs and the max-cut problem
- A class of facet producing graphs for vertex packing polyhedra
- On certain polytopes associated with graphs
- On the symmetric travelling salesman problem I: Inequalities
- Facets of the Bipartite Subgraph Polytope
- Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
- Multi-Terminal Network Flows
- Edge-Deletion Problems
- Set Partitioning: A survey
- Algorithmic Aspects of Vertex Elimination on Graphs
- On the cut polytope
- On the facial structure of set packing polyhedra
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
