A new simple parallel tree contraction scheme and its application on distance-hereditary graphs

Sun Yuan Hsieh, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko, Gen Huey Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationSolving Irregularly Structured Problems in Parallel - 5th International Symposium, IRREGULAR 1998, Proceedings
PublisherSpringer Verlag
Pages298-309
Number of pages12
ISBN (Print)3540648097, 9783540648093
DOIs
Publication statusPublished - 1998 Jan 1
Event5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998 - Berkeley, CA, United States
Duration: 1998 Aug 91998 Aug 11

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1457 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Symposium on Solving Irregularly Structured Problems in Parallel, IRREGULAR 1998
CountryUnited States
CityBerkeley, CA
Period98-08-0998-08-11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new simple parallel tree contraction scheme and its application on distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this