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

      0 references
      0 references
      1987
      0 references
      routing region
      0 references
      rectangular grid
      0 references
      local routing
      0 references
      edge-disjoint
      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

      Identifiers