Constant Time Generation of Trees with Degree Bounds
スポンサーリンク
概要
- 論文の詳細を見る
Given a number n of vertices, a lower bound d on the diameter, and a capacity function Δ(k) ? 2, k = 0, 1, . . . , n/2, we consider the problem of enumerating all unrooted trees T with exactly n vertices and a diameter at least d such that the degree of each vertex with distance k from the center of T is at most Δ(k). 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.
- 2010-09-15
著者
-
Bingbing Zhuang
Graduate School of Informatics, Kyoto University
-
Hiroshi Nagamochi
Graduate School of Informatics, Kyoto University
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nagamochi
Graduate School Of Informatics Kyoto University
-
Nagamochi Hiroshi
Graduate School Of Informatics Kyoto University
-
Hiroshi Nagamochi
Department Of Applied Mathematics And Physics Kyoto University
-
Bingbing Zhuang
Graduate School Of Informatics Kyoto University
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Zhuang Bingbing
Graduate School Of Informatics Kyoto University
関連論文
- Constant Time Generation of Trees with Degree Bounds
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- Survivable Network Design Problems with Weighted Degree Constraints (Combinatorial Optimization and Discrete Algorithms)
- Contention-Free λ-Planes in Optically Burst-Switched WDM Networks(Internet)
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- Protein complex prediction via improved verification methods using constrained domain-domain matching
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Indexing All Rooted Subgraphs of a Rooted Graph
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS