Name
Title | ||
|---|---|---|
On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths. Extended Abstract |
Abstract | ||
|---|---|---|
In this paper we show that the routing permutation problem is NP-hard even for binary trees. Moreover, we show that in the
case of unbounded degree tree networks, the routing permutation problem is NP-hard even if the permutations to be routed are
involutions. Finally, we show that the average-case complexity of the routing permutation problem on linear networks is n/4 + o(n).
|
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/10719839_32 | LATIN |
Keywords | Field | DocType |
np-completeness.,arc-disjoint paths,path col- oring,extended abstract,average-case complexity,routing permutations,tree networks,binary tree,col | Discrete mathematics,Average-case complexity,Range tree,Combinatorics,Tree traversal,Computer science,K-ary tree,Permutation,Optimal binary search tree,Binary tree,Random binary tree | Conference |
Volume | ISSN | ISBN |
1776 | 0302-9743 | 3-540-67306-7 |
Citations | PageRank | References |
2 | 0.39 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dominique Barth | 1 | 41 | 4.29 |
| Sylvie Corteel | 2 | 266 | 36.33 |
| Alain Denise | 3 | 366 | 28.25 |
| Danièle Gardy | 4 | 411 | 76.32 |
| Mario Valencia-Pabon | 5 | 106 | 15.57 |