Characterization of efficiently solvable problems on distance-hereditary graphs

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

doi:10.1007/3-540-49381-6_28

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	https://doi.org/10.1007/3-540-49381-6_28
出版狀態	已出版 - 1998
事件	9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of 持續時間: 14 12月 1998 → 16 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/98 → 16/12/98

存取文件

10.1007/3-540-49381-6_28

引用此

Hsieh, S. Y., Ho, C. W., Hsu, T. S., Ko, M. T., & Chen, G. H. (1998). Characterization of efficiently solvable problems on distance-hereditary graphs. 於 Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings (頁 257-266). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 1533 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49381-6_28

Hsieh, Sun Yuan ; Ho, Chin Wen ; Hsu, Tsan Sheng 等. / Characterization of efficiently solvable problems on distance-hereditary graphs. Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Springer Verlag, 1998. 頁 257-266 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{906b41f9fc174298a51f316023004d21,

title = "Characterization of efficiently solvable problems on distance-hereditary graphs",

abstract = "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.",

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/3-540-49381-6_28",

language = "???core.languages.en_GB???",

isbn = "3540653856",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "257--266",

booktitle = "Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings",

note = "null ; Conference date: 14-12-1998 Through 16-12-1998",

}

Hsieh, SY, Ho, CW, Hsu, TS, Ko, MT & Chen, GH 1998, Characterization of efficiently solvable problems on distance-hereditary graphs. 於 Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 卷 1533 LNCS, Springer Verlag, 頁 257-266, 9th Annual International Symposium on Algorithms and Computation, ISAAC'98, Taejon, Korea, Republic of, 14/12/98. https://doi.org/10.1007/3-540-49381-6_28

Characterization of efficiently solvable problems on distance-hereditary graphs. / Hsieh, Sun Yuan; Ho, Chin Wen; Hsu, Tsan Sheng 等.

Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Springer Verlag, 1998. p. 257-266 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 1533 LNCS).

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

TY - GEN

T1 - Characterization of efficiently solvable problems on distance-hereditary graphs

AU - Hsieh, Sun Yuan

AU - Ho, Chin Wen

AU - Hsu, Tsan Sheng

AU - Ko, Ming Tat

AU - Chen, Gen Huey

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=22644447457&partnerID=8YFLogxK

U2 - 10.1007/3-540-49381-6_28

DO - 10.1007/3-540-49381-6_28

M3 - 會議論文篇章

AN - SCOPUS:22644447457

SN - 3540653856

SN - 9783540653851

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 257

EP - 266

BT - Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings

PB - Springer Verlag

Y2 - 14 December 1998 through 16 December 1998

ER -

Hsieh SY, Ho CW, Hsu TS, Ko MT, Chen GH. Characterization of efficiently solvable problems on distance-hereditary graphs. 於 Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Springer Verlag. 1998. p. 257-266. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49381-6_28

Characterization of efficiently solvable problems on distance-hereditary graphs

摘要

出版系列

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

存取文件

指紋

引用此