ISSN:
1432-0541
Schlagwort(e):
Edge ranking
;
Minimum height edge-separator
;
Node ranking
;
Trees
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking isoptimal if the highest label used is as small as possible. The edge-ranking problem has applications in scheduling the manufacture of complex multipart products; it is equivalent to finding the minimum height edge-separator tree. In this paper we give the first polynomial-time algorithm to find anoptimal edge ranking of a tree, placing the problem inP. An interesting feature of the algorithm is an unusual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. AnNC algorithm is presented that finds an optimal edge ranking for trees of constant degree. We also prove that a natural decision problem emerging from our sequential algorithm isP-complete.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01189071
Permalink
