@inproceedings{a386759f1eaf4587af686b764a1d1c3a,
title = "A new simple parallel tree contraction scheme and its application on distance-hereditary graphs",
abstract = "We present a new parallel tree contraction scheme which takes O(log n) contraction phases to reduce a tree to its root, and implement this scheme in O(log n log log n) time using O(n/log log n) processors on an arbitrary CRCW PRAM. We then show a data structure to represent a connected distance-hereditary graph G in the form of a rooted tree. Applying our tree contraction scheme on the above data structure together with graph theoretical properties, we solve the problems of finding a minimum connected γ-dominating set and finding a minimum γ-dominating clique on G in O(log n log log n) time using O((n + m)/log log n) processors on an arbitrary CRCW PRAM, where n and m are the number of vertices and edges in G, respectively.",
author = "Hsieh, {Sun Yuan} and Ho, {Chin Wen} and Hsu, {Tsan Sheng} and Ko, {Ming Tat} and Chen, {Gen Huey}",
year = "1998",
doi = "10.1007/bfb0018548",
language = "???core.languages.en_GB???",
isbn = "3540648097",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "298--309",
booktitle = "Solving Irregularly Structured Problems in Parallel - 5th International Symposium, IRREGULAR 1998, Proceedings",
note = "5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998 ; Conference date: 09-08-1998 Through 11-08-1998",
}