Enumerating Colored and Rooted Outerplanar Graphs
スポンサーリンク
概要
- 論文の詳細を見る
An outerplanar graph is a graph that admits a planar embedding such that all vertices appear on the boundary of its outer face. Given a positive integer n and a color set C with K ? 1 colors, we consider the problem of enumerating all colored and rooted outerplanar graphs with at most n vertices without repetition. We design an efficient algorithm that can generate all required graphs in O(1) time per each and in O(n) space.
- 一般社団法人情報処理学会の論文
- 2010-02-26
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Nagamochi Hiroshi
Graduate School Of Informatics Kyoto University
-
Hiroshi Nagamochi
Department Of Applied Mathematics And Physics Kyoto University
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Jiexun Wang
Department of Applied Mathematics and Physics, Kyoto University
-
Wang Jiexun
Department Of Applied Mathematics And Physics Kyoto University
-
Jiexun Wang
Department Of Applied Mathematics And Physics Kyoto University
-
Hiroshi Nagamochi
Department Of Applied Mathematics And Physics 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