On-line Matching Routing on Trees

Alan Roberts and Antonios Symvonis 1

Department of Computer Science, University of Sydney, NSW 2006, Australia. falanr,[email protected]

Abstract

In this paper we examine on-line heap construction and on-line permutation routing on trees under the matching model. Let T be and n-node tree of maximum degree d. By providing on-line algorithms we prove that:

(i) For a rooted tree of height h, on-line heap construction can be completed within (2d ? 1)h routing steps.

(ii) For an arbitrary tree, on-line permutation routing can be completed within 4dn routing steps.

(iii) For a complete d-ary tree, on-line permutation routing can be completed within 2(d?1)n+ 2d log2 n routing steps.

Technical Report 514
Basser Department of Computer Science
University of Sydney
Original: 27 May 1997

1 The work of Dr Symvonis was supported by an ARC Institutional Grant.

27 May 1997