Enumerating All Rooted Trees Including <i>k</i> Leaves

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly n vertices including exactly k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

• 2010-09-15

著者

• Masanobu Ishikawa

  Department of Computer Science, Gunma University.

• Katsuhisa Yamanaka

  Graduate School of Information Systems, University of Electro-communications.

• Yota Otachi

  Graduate School of Information Sciences, Tohoku University.

• Shin-ichiNakano

  Department of Computer Science, Gunma University.

• Yota Otachi

  Graduate School Of Information Sciences Tohoku University.

• Masanobu Ishikawa

  Department Of Computer Science Gunma University.

• Katsuhisa Yamanaka

  Graduate School Of Information Systems University Of Electro-communications.

関連論文

• Enumerating All Rooted Trees Including k Leaves
• Computational Complexities of University Interview Timetabling
• Random Generation and Enumeration of Proper Interval Graphs
• Efficient Enumeration of All Ladder Lotteries with k Bars
• Efficient Enumeration of All Pseudoline Arrangements
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• A Compact Encoding of Rectangular Drawings with Edge Lengths
• Approximating the path-distance-width for k-cocomparability graphs
• Coding Ladder Lotteries

スポンサーリンク