No label defined (Q3777475)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4039320
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4039320 |
Statements
1987
0 references
routing region
0 references
rectangular grid
0 references
local routing
0 references
edge-disjoint
0 references
0.9041644334793092
0 references
0.8371422290802002
0 references
0.826790988445282
0 references
0.8231827616691589
0 references
[For the entire collection see Zbl 0604.00016.] A routing region R is a finite subgraph of the planar rectangular grid. Let B be the set of vertices of R with degree at most three. A local routing is a path in the routing region R connecting two vertices of B. The authors consider the following problem: Given a routing region R, a set N of pairs of vertices in B and a natural number k, find edge- disjoint local routings connecting each pair in N such that the total length of the local routings is not greater than k. Let n denote k plus the number of vertices of R. The authors show that in O(n 2) time, one can decide whether the above problem has a solution and can also construct a solution if it does.
0 references