Title :
A polynomial algorithm for the MIN CUT linear arrangement of trees
Author :
Yannakakis, Mihalis
Abstract :
An algorithm is presented which finds a min-cut linear arrangement of a tree in O(nlogn) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.
Keywords :
Bandwidth; Circuits; Cost function; Joining processes; Minimization; Polynomials; Tree graphs; Very large scale integration; Wires;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.2
