scientific article; zbMATH DE number 4039320

From MaRDI portal
Publication:3777475





[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.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777475)