𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The stable set problem and the thinness of a graph

✍ Scribed by Carlo Mannino; Gianpaolo Oriolo; Federico Ricci; Sunil Chandran

Publisher
Elsevier Science
Year
2007
Tongue
English
Weight
207 KB
Volume
35
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Stability critical graphs and ranks face
Stability critical graphs and ranks facets of the stable set polytope
✍ E.C. Sewell; L.E. Trotter Jr. πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 616 KB

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (we

A study on the tie-set graph theory and
A study on the tie-set graph theory and network flow optimization problems
✍ Toshio Koide; Haruki Kubo; Hitoshi Watanabe πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 198 KB πŸ‘ 2 views

## Abstract Aiming at establishing a firm basic theory to ring‐based information network management systems, our paper proposes a tie‐set graph theory. We define a binary vector representing a tie‐set in a biconnected undirected graph __G__=(__V__,__E__) as a tie‐set vector. The set of tie‐set vect

On the nonseparating independent set pro
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.

Blocking Systems of a Graph and βˆͺ ∩ Inte
Blocking Systems of a Graph and βˆͺ ∩ Interchange Equality in Bottleneck Problems Involving Sets and Fuzzy Sets
✍ Kenji Onaga; Shu Park Chan πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 661 KB

A blocking system (9, 2Q of a finite set E of objects is two families of non-comparable subsets of E satisfying the non-empty intersection property and the sample set inclusion property. This paper presents nine new examples, and proves 17 U -interchange equality. As applications, bottleneck problem