Listing All Connected Plane Triangulations(Algorithms and Data Structures)
スポンサーリンク
概要
- 論文の詳細を見る
A "rooted" plane triangulation is a plane triangulation with one designated vertex r and one designated edge incident to r on the outer face. In this paper we give a simple algorithm to generate all connected rooted plane triangulations with at most m edges. The algorithm uses O(m) space and generates such triangulations in O(l) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all connected (non-rooted) plane triangulations with at most m edges in O(m^3) time per triangulation.
- 社団法人電子情報通信学会の論文
- 2003-07-01
著者
-
Nakano Shin-ichi
Department Of Anesthesiology Kansai Medical University
-
Nakano Shin-ichi
Department Of Computer Science Faculty Of Engineering Gunma University
-
LI Zhang-Jian
Department of Computer Science, Faculty of Engineering, Gunma University
-
Li Zhang-jian
Department Of Computer Science Faculty Of Engineering Gunma University
関連論文
- Constant Time Generation of Integer Partitions(Discrete Mathematics and Its Applications)
- Successful management of cesarean section in a patient with Romano-Ward syndrome using landiolol, a selective and short-acting β1 receptor antagonist
- An antagonistic effect of esmolol on beta-3 adrenoceptor in brown adipose tissue in rats
- Anticonvulsant effects of sevoflurane on amygdaloid kindling and bicuculline-induced seizures in cats: comparison with isoflurane and halothane
- An unusual case of airway obstruction at the tip of an endotracheal tube caused by insertion of a nasogastric tube
- A Simple Canonical Code for Fullerene Graphs
- Effects of propofol and thiopental on the central nervous system during nociceptive stimulation in cats
- Satellite Cell Differentiation in Goat Skeletal Muscle Single Fiber Culture
- Efficient Generation of Plane Triangulations with Specified Maximum Degree(Foundations of Computer Science)
- A Compact Encoding of Rectangular Drawings with Efficient Query Supports
- Constant Time Generation of Rectangular Drawings with Exactly n Faces(Algorithms and Data Structures)
- Coding Floorplans with Fewer Bits(Discrete Mathematics and Its Applications)
- A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs (Special Section on Discrete Mathematics and Its Applications)
- Growth Dependence of Reactively Sputtered Yttria-Stabilized Zirconia on Si(100), (110), (111) Substrates
- Efficient Generation of Plane Triangulations with a Degree Constraint
- Listing All Rectangular Drawings with Some Properties
- An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
- Listing All Connected Plane Triangulations(Algorithms and Data Structures)
- Special Section on Foundations of Computer Science
- Generating Biconnected Plane Quadrangulations
- The Vertical Distribution of Pearl Oyster Pinctada fucata martensii Spat in Uchiumi Bay
- Special Section on Discrete Mathematics and Its Applications
- A compact encoding of rectangular drawings with edge lengths (コンピュテーション)
- A Compact Encoding of Rectangular Drawings with Edge Lengths
- Listing All st-Orientations
- Establishment of bipotent progenitor cell clone from rat skeletal muscle
- Enumerating All Rooted Trees Including k Leaves
- In Vivo Electroporation Induces Cell Cycle Reentry of Myonuclei in Rat Skeletal Muscle
- A Compact Encoding of Rectangular Drawings with Edge Lengths
- Two Compact Codes for Rectangular Drawings with Degree Four Vertices
- Another Optimal Binary Representation of Mosaic Floorplans