2007年
An efficient algorithm for generating colored outerplanar graphs
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS
- ,
- ,
- ,
- 巻
- 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