𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of some edge-partition problems for graphs

✍ Scribed by Zbigniew Lonc

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
515 KB
Volume
70
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the complexity of graph tree partitio
On the complexity of graph tree partition problems
✍ Roberto Cordone; Francesco Maffioli πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 270 KB

This paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider di erent objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunicati

Partitioning the edge set of a bipartite
Partitioning the edge set of a bipartite graph into chain packings: complexity of some variations
✍ D. de Werra πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 154 KB

An extension of the decomposition theorem of Birkhoff-von Neumann theorem is given for the case where entries can be positive or negative. The special case of an integral matrix is discussed and some balancing properties which are trivial for the classical case (non-negative entries only in the matr

On partitioning the edges of graphs into
On partitioning the edges of graphs into connected subgraphs
✍ M. JΓΌnger; G. Reinelt; W. R. Pulleyblank πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 559 KB

For any positive integer s, an s-partition of a graph G = ( ! -( €I is a partition of E into El U E2 U U E k, where 14 = s for 1 I i 5 k -1 and 1 5 1 4 1 5 s and each €; induces a connected subgraph of G. We prove (i) if G is connected, then there exists a 2-partition, but not neces-(ii) if G is 2-e