Maximum edge-disjoint paths problem in planar graphs

被引：0

作者：

Xia, Mingji ^{[1
]}

机构：

[1] Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing 100080, Peoples R China

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS | 2007年 / 4484卷

关键词：

maximum edge-disjoint paths; determinant; #P-hard;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a randomized algorithm for maximum edge-disjoint paths problem (MEDP) and the minimal total length of MEDP, if the graphs are planar and all terminals lie on the outer face in the order (s1,) (s2, . . . sk, tk, tk-1, . . .) (t1). Moreover, if the degree of the graph is bounded by 3, the algorithm becomes deterministic and can also output the number of optimal solutions. On the other hand, we prove that the counting version of these problems are #P-hard even if restricted to planar graphs with maximum degree 3.

引用

页码：566 / 572

页数：7

共 17 条

[1] BRANDES U, 1996, EDGE DISJOINT PATHS
[2] STATISTICAL MECHANICS OF DIMERS ON A PLANE LATTICE
FISHER, ME
[J]. PHYSICAL REVIEW, 1961, 124 (06): : 1664 - &
[3] STATISTICS OF DIMERS ON A LATTICE .1. NUMBER OF DIMER ARRANGEMENTS ON A QUADRATIC LATTICE
KASTELEYN, P
[J]. PHYSICA, 1961, 27 (12): : 1209 - +
[4] Kasteleyn P., 1967, Graph Theory and Theoretical Physics, P1
[5] ON THE COMPLEXITY OF THE DISJOINT PATHS PROBLEM
MIDDENDORF, M
PFEIFFER, F
[J]. COMBINATORICA, 1993, 13 (01) : 97 - 107
[6] Papadimitriou CH., 1994, Computational Complexity
[7] Schrijver A, 2003, Algorithms and Combinatorics
[8] INTEGER PLANE MULTIFLOWS WITH A FIXED NUMBER OF DEMANDS
SEBO, A
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1993, 59 (02) : 163 - 171
[9] DIMER PROBLEM IN STATISTICAL MECHANICS - AN EXACT RESULT
TEMPERLEY, HNV
FISHER, ME
[J]. PHILOSOPHICAL MAGAZINE, 1961, 6 (68): : 1061 - 1063
[10] The complexity of counting in sparse, regular, and planar graphs
Vadhan, SP
[J]. SIAM JOURNAL ON COMPUTING, 2001, 31 (02) : 398 - 427

← 1 2 →