Name
Abstract | ||
|---|---|---|
The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two algorithms in NC. The first solves the minimum length linear arrangement problem for unrooted trees in $O(\log^2 n)$ time and $O(n^2 3^{\log n})$ CREW PRAM processors. The second algorithm solves the minimum cut arrangement for unrooted trees of maximum degree $d$ in $O(d \log^2 n)$ time and $O(n^2 /\log n)$ CREW PRAM processors. |
Year | Venue | Keywords |
|---|---|---|
1995 | COCOON '95 Proceedings of the First Annual International Conference on Computing and Combinatorics | unrooted tree,general graph,maximum degree,efficient parallel algorithms,crew pram processor,minimum cut arrangement,minimum cut,linear arrangement problem,minimum length,wiring problem,tree layout problems,log n,parallel algorithm |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Parallel algorithm,Computer science,Tree decomposition,Minimum cut,Gomory–Hu tree,Minimum k-cut,Minimum spanning tree,Cost efficiency,Bounded function | Conference | 959 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-60216-X | 1 |
PageRank | References | Authors |
0.63 | 5 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Diaz | 1 | 1 | 0.63 |
| A. Gibbons | 2 | 11 | 2.77 |
| Grammati E. Pantziou | 3 | 366 | 42.33 |
| M. Serna | 4 | 31 | 4.28 |
| Paul G. Spirakis | 5 | 2222 | 299.05 |
| Jacobo Torán | 6 | 26 | 5.68 |