Name
Abstract | ||
|---|---|---|
In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n3) and the maximum path length 3n + 4. We conducted a computer experiment for n = 2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n3.0) and the maximum path length is 3n + 4. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1093/ietisy/e90-1.1.306 | IEICE Transactions |
Keywords | Field | DocType |
node-to-node disjoint paths problem,burnt pancake graphs,average time complexity,time complexity o,polynomial-order time,average performance,computer experiment,n-burnt pancake graph,maximum path length | Computer experiment,Discrete mathematics,Graph,Combinatorics,Disjoint sets,Path length,Correctness,Algorithm,Floyd–Warshall algorithm,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
E90-D | 1 | 1745-1361 |
Citations | PageRank | References |
11 | 0.57 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keiichi Kaneko | 1 | 189 | 39.19 |
| Naoki Sawada | 2 | 16 | 5.06 |