On packing connectors (Q1272488): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: J. C. M. Keijsper / rank | |||
Property / author | |||
Property / author: Alexander Schrijver / rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Property / author | |||
Property / author: J. C. M. Keijsper / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Alexander Schrijver / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Heinz Joachim Presia / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1998.1825 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2165714486 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Packing Spanning Trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5580173 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An efficient algorithm for minimum-weight bibranching / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge-Disjoint Spanning Trees of Finite Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Min-max Relations for Directed Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3818127 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Problem of Decomposing a Graph into <i>n</i> Connected Factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111952 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:43, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On packing connectors |
scientific article |
Statements
On packing connectors (English)
0 references
8 March 1999
0 references
Let \(G=(V,E)\) be an undirected graph and \(\{S,T\}\) a partition of \(V\). Then a set of edges \(F\subseteq E\) such that every component of the subgraph \((V,F)\) intersects both \(S\) and \(T\), is called an \(S\)--\(T\) connector. In general a subpartition \(W\) of a set \(X\) is a collection of pairwise disjoint nonempty subsets of \(X\); and if---like in the present case---\(W=\{U_1, \dots, U_t\}\) is a subpartition of \(S\) or \(T\), then \(\delta(W)\) denotes the set of edges with one end in \(U_i\) and one end in \(V\setminus U_i\) for some index \(i\). The main result of this paper is Theorem 1: \(G\) contains \(k\) edge-disjoint \(S\)--\(T\) connectors iff \(|\delta (W)|\geq k\cdot | W|\) for every subpartition \(W\) of \(S\) or \(T\), where \(k\) is a natural number. This result is a generalization of a theorem on (i) disjoint edge covers in a bipartite graph (König/Gupta), and (ii) disjoint spanning trees in an undirected graph (Tutte/Nash-Williams), stated here as Lemma 1. According to the concept of \(S\)--\(T\) connector in undirected graphs the \(S\)--\(T\) bibranching is defined in directed graphs and a result of Schrijver with respect to packing bibranches is given as Lemma 2. The proof of Theorem 1 follows essentially by combining both these lemmas. Simultaneously this proof yields the basis for a polynomial algorithm for packing \(S\)--\(T\) connectors not described in the present paper. Finally, in Section 3, it is shown that Theorem 1 implies the integer rounding property for a set of linear inequalities associated with packing \(S\)--\(T\) connectors. The polyhedral formulation of this fact is given in Theorem 2.
0 references
partition
0 references
connector
0 references
packing bibranches
0 references