論文

査読有り
2010年

Generating Trees on Multisets

ALGORITHMS AND COMPUTATION, PT I
  • Bingbing Zhuang
  • ,
  • Hiroshi Nagamochi

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

エクスポート
BibTeX RIS