A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs
スポンサーリンク
概要
- 論文の詳細を見る
Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/ log n) processors on EREW PRAM computation model.
著者
-
Masuyama Shigeru
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
Nakajima Yoko
Department Of Biology Keio University
-
Honma Hirotoshi
Department Of Information Engineering Kushiro National College Of Technology
-
MASUYAMA Shigeru
Department of Computer Science and Engineering, Toyohashi University of Technology
-
AOSHIMA Haruka
Electronic Information System Engineering Course, Kushiro National College of Technology
関連論文
- NGIWYamide-induced Contraction of Tube Feet and Distribution of NGIWYamide-like Immunoreactivity in Nerves of the Starfish Asterina pectinifera(Physiology)
- A New Aspect of the Carotid Body Function Controlling Hypoxic Ventilatory Decline in Humans
- The Inhibition of Motility of Demembranated Spermatozoa by Anti-tubulin Antibodies
- Acylcarnitine Profiles during Carnitine Loading and Fasting Tests in a Japanese Patient with Medium-Chain Acyl-CoA Dehydrogenase Deficiency
- An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
- An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph
- Detection of Pivaloylcarnitine in Pediatric Patients with Hypocarnitinemia after Long-Term Administration of Pivalate-Containing Antibiotics
- Cause Information Extraction from Financial Articles Concerning Business Performance
- Adhesive papillae on the brachiolar arms of brachiolaria larvae in two starfishes, Asterina pectinifera and Asterias amurensis, are sensors for metamorphic inducing factor(s)
- METAMORPHOSIS IN STARFISH : DEPENDENCY ON FORMATION OF ATTACHMENT ORGANS AND FLEXIBILITY OF ADULT RUDIMENT FORMATION FOR THE TIMING OF METAMORPHOSIS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Societ
- THE ADULT RADIAL NERVE EXTRACT CAN INDUCE METAMORPHOSIS IN THE COMPETENT LARVAE OF STARFISH, ASTERIANA PECTINIFERA(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
- A MONOCLONAL ANTIBODY IDENTIFIES A PECULIAR ECTODERMAL CELL POPULATION IN THE BRACHIOLARIA OF THE STARFISH, ASTERINA PECTINIFERA(Developmental Biology,Abstracts of papers presented at the 74^ Annual Meeting of the Zoological Society of Japan)
- CELL-BEHAVIOR DATABASE(Cell Biology and Morphology,Abstracts of papers presented at the 74^ Annual Meeting of the Zoological Society of Japan)
- A case of holocarboxylase synthetase deficiency with insufficient response to prenatal biotin therapy
- Control of Upper Airway Function in Response to Hypoxia in Patients with Obstructive Sleep Apnea Syndrome
- Compensatory Excretion of Prostacyclin and Thromboxane Metabolites in Obstructive Sleep Apnea Syndrome
- DEVELOPMENT OF THE NERVOUS SYSTEM OF THE STALKED CRINOID ECHINODERM, METACRINUS ROTUNDUS(Taxonomy and Systematics,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
- The Effect of Changing Rate of PIO_2 Fall on Relationship between Ventilatory and Heart Rate Response to Progressive Hypoxia
- Analysis of Heart Rate Profile during Obstructive Sleep Apnea
- Properties on the Average Number of Spanning Trees in Connected Spanning Subgraphs for an Undirected Graph
- Formulas for Counting the Numbers of Connected Spanning Subgraphs with at Most n+1 Edges in a Complete Graph K_n
- PROPASAL OF THE UNRESTRICTED LR(k) GRAMMAR AND ITS PARSER
- Primary mesenchyme cell-ring pattern formation in 2D-embryos of the sea urchin
- Development and Neural Organization of the Tornaria Larva of the Hawaiian Hemichordate, Ptychodera flava(Developmental Biology)
- Parieto-occipital encephalomalacia in neonatal hyperammonemia with ornithine transcarbamylase deficiency : A case report
- Determination of 3-hydroxyisovalerylcarnitine and other acylcarnitine levels using liquid chromatography-tandem mass spectrometry in serum and urine of a patient with multiple carboxylase deficiency
- A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs(Invited Papers from New Horizons in Computing)
- STRUCTURE OF THE NERVOUS SYSTEM OF THE BRACHIOLARIA LARVAE OF ASTEROIDS, ASSOCIATED WITH THEIR ATTACHMENT ORGANS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
- An Informative DOM Subtree Identification Method from Web Pages in Unfamiliar Web Sites
- Formulation of Mobile Agent Allocation and Its Strong NP-Completeness(Complexity Theory)
- Novel Structures in Secreting the Androgenic Gland Hormone(Reproductive Biology)
- Multiple Document Summarization System GOLD(Special Issue on Text Processing for Information Access)
- UGLR Parser for Phrase Structure Languages as an Extension of GLR Parser (Special Section on Discrete Mathematics and Its Applications)
- T1 MINIMUM VERTEX RANKING SPANNING TREE PROBLEM : A TUTORIAL(Tutorial speech)
- A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
- A Statistical Method for Acquiring Knowledge about the Abbreviation Possibility of Some of Multiple Adnominal Phrases(Special Issue on Text Processing for Information Access)
- A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs
- An Algorithm for Solving the Minimum Vertex Ranking Spanning Tree Problem on Interval Graphs
- MINIMUM DELAY SEMIJOIN SCHEDULES FOR LOCAL AREA DISTRIBUTED DATABASE SYSTEMS(Mathematical Theories on Computing Schemes and Their Applications)
- Assigning Polarity to Causal Information in Financial Articles on Business Performance of Companies
- An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs
- On the Largest Common Subgraph Problem
- Efficient Algorithm for Minimum Feedback Vertex Set Problem on Trapezoid Graphs
- Function and Localization of Microtubules in the Lens
- An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
- Biodiversity of Echinoderm Larval Nervous System(Perspective of Neurogenesis Research in Invertebrates: a Comparison between Deuterostomes and Protostomes,Symposium,PROCEEDING OF THE 75^ ANNUAL MEETING OF THE ZOOLOGICAL SOCIETY OF JAPAN)
- IS2-05 Children undergoing LRLTx for treatment of Inherited-Metabolic Diseases are prone to higher oxidative stress and complement activity
- Evaluation of valproate effects on acylcarnitine in epileptic children by LC-MS/MS
- Automatic Construction of Train Arrival and Departure Schedules at Terminal Stations
- Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation Graphs
- A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs
- 4A3 AN ONLINE SCHEDULING ALGORITHM THAT MINIMIZES THE TOTAL COMPLETION TIME IN AN AGV SYSTEM AND ITS COMPETITIVE ANALYSIS(Technical session 4A: Material handling system)
- 5A2 AUTOMATIC CONSTRUCTION OF TRAIN ARRIVAL AND DEPARTURE SCHEDULES IN TERMINAL STATIONS(Technical session 5A: OS4: Railway scheduling)