| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
A Splitting Lemma | G. Greco
; | Date: |
3 Dec 2003 | Subject: | Combinatorics MSC-class: 05C70;05d05;68R01 | math.CO | Abstract: | In this paper, we study the relations between the numerical structure of the optimal solutions of a convex programming problem defined on the edge set of a simple graph and the stability number (i.e. the maximum size of a subset of pairwise non-adjacent vertices) of the graph. Our analysis shows that the stability number of every graph G can be decomposed in the sum of the stability number of a subgraph containing a perfect 2-matching (i.e. a system of vertex-disjoint odd-cycles and edges covering the vertex-set) plus a term computable in polynomial time. As a consequence, it is possible to bound from above and below the stability number in terms of the matching number of a subgraph having a perfect 2-matching and other quantities computable in polynomial time. Our results are closely related to those by Lorentzen, Balinsky, Spielberg, and Pulleyblank on the linear relaxation of the vertex-cover problem. Moreover, The convex programming problem involved has important applications in information theory and extremal set theory where, as a graph capacity formula, has been used to answer a longstanding open question about qualitatively independet sets in the sense of Renyi (L. Gargano, J. K{örner, and U. Vaccaro, "Sperner capacities", Graphs and combinatorics, 9:31-46, 1993). | Source: | arXiv, math.CO/0312086 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |