ON LOCAL ROUTING OF 2-TERMINAL NETS

被引：4

作者：

KAUFMANN, M

MEHLHORN, K

机构：

[1] Max-Planck-Institut für Informatik

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1992年 / 55卷 / 01期

关键词：

D O I：

10.1016/0095-8956(92)90031-R

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We examine the problem of finding edge-disjoint paths between pairs of vertices placed on inner as well as outer faces of a finite grid graph. For each path a global routing, which fixes the topology of the path relative to the nontrivial faces, is part of the input. We give necessary and sufficient conditions for the solvability of the problem and provide an algorithm to find a solution with running time quadratic in the size of the problem. © 1992.

引用

页码：33 / 72

页数：40

共 18 条

[1]

[Anonymous], 1984, ADV COMPUTING RES

[2] ALGORITHMS FOR ROUTING IN PLANAR GRAPHS [J].