@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",
}