論文

査読有り
2007年

An efficient algorithm for generating colored outerplanar graphs

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS
  • Jiexun Wang
  • ,
  • Liang Zhao
  • ,
  • Hiroshi Nagamochi
  • ,
  • Tatsuya Akutsu

4484
開始ページ
573
終了ページ
+
記述言語
英語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.1007/978-3-540-72504-6_52
出版者・発行元
SPRINGER-VERLAG BERLIN

Given two integers n and m with 1 <= m <= n, we consider the problem of generating nonisomorphic colored outerplanar graphs with at most n vertices, where each outerplanar graph is colored with at most m colors. In this paper, we treat outerplanar graphs as rooted outerplane graphs, i.e., plane embeddings with a designated vertex as the root, and propose an efficient algorithm for generating all such colored graphs based on a unique representation of those embeddings. Our algorithm runs in O(n) space and outputs all colored and rooted outerplane graphs without repetition in O(1) time per graph.

リンク情報
DOI
https://doi.org/10.1007/978-3-540-72504-6_52
DBLP
https://dblp.uni-trier.de/rec/conf/tamc/WangZNA07
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000246671900052&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/conf/tamc/tamc2007.html#conf/tamc/WangZNA07
ID情報
  • DOI : 10.1007/978-3-540-72504-6_52
  • ISSN : 0302-9743
  • DBLP ID : conf/tamc/WangZNA07
  • Web of Science ID : WOS:000246671900052

エクスポート
BibTeX RIS