✦ LIBER ✦

A Faster Implementation of a Parallel Tree Contraction Scheme and Its Application on Distance-Hereditary Graphs

✍ Scribed by Sun-yuan Hsieh; Chin-Wen Ho; Tsan-sheng Hsu; Ming-Tat Ko; Gen-Huey Chen

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 261 KB
Volume: 35
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1064

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a parallel tree contraction scheme which in each contraction phase Ž . Ž . removes leaves and nodes in the maximal chains. Let T n and P n denote the time and processor complexity required to compute the all nearest smaller values Ž . ANSV and the minimum of n values for input elements drawn from the integer 1 A preliminary version of this paper appeared in ''Proceedings of 5th International Ž .