scientific article; zbMATH DE number 4039320
[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.
- Algorithms for routing in planar graphs
- Edge-disjoint homotopic paths in a planar graph with one hole
- Routing in polygons without rectilinearly visible corners
- On local routing of two-terminal nets
- Call routing and the ratcatcher
- Local routing in a tree metric 1-spanner
- scientific article; zbMATH DE number 4191147 (Why is no real title available?)
- scientific article; zbMATH DE number 4051669 (Why is no real title available?)
- On the routability of a convex grid
- scientific article; zbMATH DE number 1762482 (Why is no real title available?)
- Brief announcement: What can(not) be perfectly rerouted locally
- Decomposition of graphs on surfaces and a homotopic circulation theorem
- Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI
- Routing with critical paths
- A generic algorithm for one-dimensional homotopic compaction
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)