A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.
- 社団法人電子情報通信学会の論文
- 2001-05-01
著者
-
Nagai Sayaka
Department of Applied Chemistry, Faculty of Science and Engineering, Kinki University
-
Nagai S
Department Of Computer Science Faculty Of Engineering Gunma University
-
Nakano S
Gunma Univ. Kiryu‐shi Jpn
-
Nakano Shin-ichi
Department Of Anesthesiology Kansai Medical University
関連論文
- Volatile Components of the Straw of Oryza sativa L.
- 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
- The Bovine Lactophorin C-Terminal Fragment and PAS6/7 Were Both Potent in the Inhibition of Human Rotavirus Replication in Cultured Epithelial Cells and the Prevention of Experimental Gastroenteritis
- 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