Characterization of efficiently solvable problems on distance-hereditary graphs

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

研究成果: 書貢獻/報告類型會議論文篇章同行評審

3 引文 斯高帕斯(Scopus)

摘要

In the literature, there are quite a few sequential and parallel algorithms to solve problems in a distance-hereditary graph G utilizing techniques discovered from the properties of the problems. Based on structural properties of G, we first sketch characteristics of problems which can be systematic solved on G and then define a general problem-solving paradigm. Given a decomposition tree representation of G, we propose a unified approach to construct sequential dynamic-programming algorithms for several fundamental graph-theoretical problems that fit into our paradigm. We also show that our sequential solutions can be efficiently parallelized using the tree contraction technique.

原文???core.languages.en_GB???
主出版物標題Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
發行者Springer Verlag
頁面257-266
頁數10
ISBN(列印)3540653856, 9783540653851
DOIs
出版狀態已出版 - 1998
事件9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of
持續時間: 14 12月 199816 12月 1998

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
1533 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???9th Annual International Symposium on Algorithms and Computation, ISAAC'98
國家/地區Korea, Republic of
城市Taejon
期間14/12/9816/12/98

指紋

深入研究「Characterization of efficiently solvable problems on distance-hereditary graphs」主題。共同形成了獨特的指紋。

引用此