A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs(<Special Section>Invited Papers from New Horizons in Computing)
スポンサーリンク
概要
- 論文の詳細を見る
The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.
- 社団法人電子情報通信学会の論文
- 2006-08-01
著者
-
Masuyama Shigeru
Department Of Knowledge-based Information Engineering Toyohashi University Of Technology
-
Masuyama Shigeru
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
Masuyama Shigeru
Toyohashi Univ. Technol. Toyohashi‐shi Jpn
-
NAKAYAMA Shin-ichi
Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Toku
-
Nakayama Shin-ichi
Department Of Mathematical Sciences Faculty Of Integrated Arts And Sciences The University Of Tokush
-
Nakayama Shin-ichi
Department Of Applied Physics Faculty Of Engineering Hokkaido University
関連論文
- A New Aspect of the Carotid Body Function Controlling Hypoxic Ventilatory Decline in Humans
- 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
- Cause Information Extraction from Financial Articles Concerning Business Performance
- 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
- 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
- A Polynomial Time Algorithm for Obtaining a Minimum Vertex Ranking Spanning Tree in Outerplanar Graphs(Invited Papers from New Horizons in Computing)
- 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)
- 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
- An Efficient Parallel Parsing Algorithm for Context-Free Languages Based on Earley's Method (Special Section on Discrete Mathematics and Its Applications)
- Minimum Vertex Ranking Spanning Tree Problem(TUTORIAL SPEECH)
- On the Ambiguity Reduction Ability of a Probabilistic Context-Free Grammar(Special Section on Discrete Mathematics and Its Applications)
- 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
- Band-Tail Characteristics in Amorphous Semiconductors Studied by the Constant-Photocurrent Method
- An Algorithm for Minimum Feedback Vertex Set Problem on a Trapezoid Graph
- Extraction of Effect and Technology Terms from a Patent Document(Theory and Methodology)
- Extraction of Effect and Technology Terms from a Patent Document
- 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)