2010年
Generating Trees on Multisets
ALGORITHMS AND COMPUTATION, PT I
- ,
- 巻
- 6506
- 号
- 開始ページ
- 182
- 終了ページ
- 193
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-642-17517-6_18
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Given a multiset M = V(1) boolean OR V(2) U ... U V(C) of n elements and a capacity function Delta : [1, C] -> [2, n - 1], we consider the problem of enumerating all unrooted trees T on M such that the degree of each vertex v is an element of V(i) is bounded from above by Delta(i). The problem has a direct application of enumerating isomers of tree-like chemical graphs. We give an algorithm that generates all such trees without duplication in O(1)-time delay per output in the worst case using O(n) space, with O(n) initial preprocessing time.
- リンク情報
-
- DOI
- https://doi.org/10.1007/978-3-642-17517-6_18
- DBLP
- https://dblp.uni-trier.de/rec/conf/isaac/ZhuangN10
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201102231380300542
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000298716000018&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/conf/isaac/isaac2010-1.html#conf/isaac/ZhuangN10
- ID情報
-
- DOI : 10.1007/978-3-642-17517-6_18
- ISSN : 0302-9743
- DBLP ID : conf/isaac/ZhuangN10
- J-Global ID : 201102231380300542
- Web of Science ID : WOS:000298716000018