𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Integer Plane Multiflows with a Fixed Number of Demands

✍ Scribed by A. Sebo

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
371 KB
Volume
59
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We give a polynomial algorithm which decides the integer solvability of multicommodity flow problems where the union of "capacity-" and "demand-edges" forms a planar graph, and the number of demand edges is bounded by a prefixed integer (k). This problem was solved earlier for (k=2) by Seymour and for (k=3) by Korach. For (k=4) much work has been done by Korach and Newmann. The main result of the present note is a polynomial algorithm that finds such a multiflow or proves that it does not exist, for arbitrary fixed (k). Middendorf and Pfeiffer have recently proved that this problem is NP-complete in general (without fixing (k) ). We actually give a more general polynomial algorithm, namely to decide whether the relation (y(G, T)=\tau(G, T)) or its weighted generalization holds for the pair ((G, T)) (where (G) is not necessarily planar), provided (|T|) is fixed, thus extending Seymour's method and result for (|T|=4). I 1993 Academic Press. Inc.

πŸ“œ SIMILAR VOLUMES

Techniques for the compression of sequen
Techniques for the compression of sequences of integer numbers and real numbers with fixed absolute precision
✍ Omar G. Stradella; Giorgina Corongiu; Enrico Clementi πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 657 KB

Algorithms to reduce the space needed to store information either in memory or magnetic media are presented. These algorithms were designed to pack and unpack two common kinds of data types: sequences of sets of integers that change in a regular fashion and real numbers of fixed absolute precision.

On graphs with a fixed number of negativ
On graphs with a fixed number of negative eigenvalues
✍ Aleksander TorgaΕ‘ev πŸ“‚ Article πŸ“… 1985 πŸ› Elsevier Science 🌐 English βš– 374 KB

Let P(n) be the class of all connected graphs having exactly n ~> 1 negative eigenvalues (including their multiplicities). In this paper we prove that the class P(n) contains only finitely many so-called canonical graphs. The analogous statement for the class Q(n) of all connected graphs having exac

Graphs embedded in the plane with a boun
Graphs embedded in the plane with a bounded number of accumulation points
✍ C. Paul Bonnington; R. Bruce Richter πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 138 KB πŸ‘ 1 views

## Abstract Halin's Theorem characterizes those infinite connected graphs that have an embedding in the plane with no accumulation points, by exhibiting the list of excluded subgraphs. We generalize this by obtaining a similar characterization of which infinite connected graphs have an embedding in

Note on the reconstruction of infinite g
Note on the reconstruction of infinite graphs with a fixed finite number of components
✍ Thomas Andreae πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 169 KB πŸ‘ 1 views

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G

Simultaneous Representation of Integers
Simultaneous Representation of Integers by a Pair of Ternary Quadratic Formsβ€”With an Application to Index Form Equations in Quartic Number Fields
✍ IstvΓ‘n GaΓ‘l; Attila Pethő; Michael Pohst πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 411 KB

Let Q 1 , Q 2 # Z[X, Y, Z] be two ternary quadratic forms and u 1 , u 2 # Z. In this paper we consider the problem of solving the system of equations (1) Q 2 (x, y, z)=u 2 in x, y, z # Z with gcd(x, y, z)=1. According to Mordell [12] the coprime solutions of can be presented by finitely many expr