@inproceedings{eb0d50e433ab478a9a30a685fe156129,

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

month = jan,

day = "1",

doi = "10.1007/bfb0018548",

language = "English",

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

address = "Germany",

note = "5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998 ; Conference date: 09-08-1998 Through 11-08-1998",

}