PRACTICAL EFFICIENCY OF THE LINEAR-TIME ALGORITHM FOR THE SINGLE SOURCE SHORTEST PATH PROBLEM
スポンサーリンク
概要
- 論文の詳細を見る
Thorup's linear-time algorithm for the single source shortest path problem consists of two phases: a construction phase of constructing a data structure suitable for a shortest path search from a given query source s; and a search phase of finding shortest paths from the query source s to all vertices using the data structure constructed in construction phase. Since once the data structure is constructed, it can be repeatedly used for shortest path searches from given query sources, Thorup's algorithm has a nice feature not only on its linear time complexity but also on its data structure suitable for a repetitive mode of queries (not single query). In this paper, we evaluate the practical efficiency of the Thorup's linear-time algorithm through computational experiments comparing with some of well known previous algorithms. In particular, we evaluate Thorup's algorithm mainly from the viewpoint of repetitive mode of queries.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
IMAI Hiroshi
Departments of Cardio-angiology and Emergency and Critical Care Medicine, Kitasato University School
-
ASANO Yasuhito
Graduate School of Informatics, Kyoto University
-
Asano Yasuhito
Graduate School Of Informatics Kyoto University
-
Asano Yasuhito
Graduate School Of Information Science The University Of Tokyo
-
Imai Hiroshi
Department Of Biological Sciences Graduate School Of Science University Of Tokyo
関連論文
- End-Tidal Carbon Dioxide Concentration Can Estimate the Appropriate Timing for Weaning Off From Extracorporeal Membrane Oxygenation for Refractory Circulatory Failure
- Patient Selection and Therapeutic Strategy for Emergency Percutaneous Cardiopulmonary System in Cardiopulmonary Arrest Patients
- Tissue factor expression demonstrates severe sinusoidal endothelial cell damage during rejection after living-donor liver transplantation
- Dual-Beam Delay Calibration for VERA
- Astrometry of H_2O Masers in Nearby Star-Forming Regions with VERA I : IRAS 16293-2422 in ρ Oph East
- Effect of Hypothermia Therapy After Outpatient Cardiac Arrest Due to Ventricular Fibrillation
- Foaming in an Aerated Stirred Tank and Its Mechanical Control
- Double-Patch Closure using Gelatin Resorcine Formol Glue of a Ventricular Septal Perforation following Acute Myocardial Infarction
- Assessment of fatty acid metabolism in taxan-induced myocardial damage with iodine-123 BMIPP SPECT : Comparative study with myocardial perfusion, left ventricular function, and histopathological findings
- Non-oxygenated, Substrate-free Hyperpotassemic Cardioplegic Solution Affords Safe Protection of the Ischemic Myocardium during Open Heart Surgery
- Intravascular large B-cell lymphoma presenting with mass lesions in the central nervous system : A report of five cases
- A Measurement of Proper Motions of SiO Maser Sources in the Galactic Center with the VLBA
- OJ-054 End-tidal CO_2 Concentration Has a Prognostic Impact of Fulminant Myocarditis Through Predicting the Clinical Recovery(Myocarditis, basic/clinical(M),Oral Presentation(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society
- OE-397 Hypothermia Treatment ; The New Strategies and Effectiveness for CPA Patients with Ventricular Fibrillation(Emergency care/CPR(01)(H),Oral Presentation(English),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- JVN Observation of H_2O Masers around the Evolved Star IRAS 22480+6002
- Four-Phase Structure of ρ Meson Coupled Skyrmions on S^3 : Particles and Fields
- Multi-Skyrmion with ρ and ω Mesons : Particles and Fields
- 5 Appropriate Indication and Therapeutic Strategy for the Use of Percutaneous Cardiopulmonary Support (POPS) in Cardiopulmonary Arrest (CPA) Patients(Symposium 6 (SY6) (IHD) : Treatment for CPA : Improving the Current Status?)(Special Program)
- Infected Papillary Fibroelastoma Attached to the Atrial Septum
- An Asian case of fibroblastic rheumatism : clinical, radiological, and histological features
- Efficient Compression of Web Graphs
- Aeration Method and Phosphate Release Behavior in Phosphate Removal by Sea Water Activated Sludge
- CHARACTERIZATION OF ORANGE-PUPA-INDUCING-FACTOR ON DIAPAUSE PUPAL COLORATION IN THE SWALLOWTAIL BUTTERFLY, PAPILIO XUTHUS L.(Physiology)(Proceedings of the Seventy-Third Annual Meeting of the Zoological Society of Japan)
- Editors' Introduction to Special Section on Discrete Algorithms and Complexity
- Compact Encoding of the Web Graph Exploiting Various Power Distributions(Discrete Mathematics and Its Applications)
- Simultaneous Measurements of Energetic O^- Ions and O Atoms in Sputtering of Zinc Oxide Target
- On the Orthogonal $L_1$ Linear Approximation of Points
- Finding Neighbor Communities in the Web Using an Inter-Site Graph(Database)
- Hormonal Control of the Orange Coloration of Diapause Pupae in the Swallowtail Butterfly, Papilio xuthus L.(Lepidoptera: papilionidae)(Endocrinology)
- Stent Grafting for Aortic Dissection
- A Case of Recurrent Localized Fibrous Mesothelioma
- Primary histiocytic sarcoma of the spleen associated with hemophagocytosis
- Magnesium Requirement for Biological Removal of Phosphate by Activated Sludge
- LOCAL MASS TRANSFER EROM A SINGLE CYLINDER AND TUBE BANKS VIBRATING SINUSOIDALLY IN A FLUID AT REST
- A Collimated Jet and an Infalling-Rotating Disk in G192.16-3.84 Traced by H_2O Maser Emission
- Cardiac function estimated by stroke volume starts to recover just after reperfusion therapy with special reference to stunning of acute myocardial infarction
- PRACTICAL EFFICIENCY OF THE LINEAR-TIME ALGORITHM FOR THE SINGLE SOURCE SHORTEST PATH PROBLEM
- Citric Acid Production by Surface Culture Using Aspergillus niger : Kinetics and Simulation
- Annual Parallax Measurements of an Infrared Dark Cloud, MSXDC G034.43+00.24 with VERA
- An Optimal Algorithm for Approximating a Piecewise Linear Function
- Partitioning a Polygonal Region into Trapezoids
- An Assessment of the Safety and Efficacy of an Indwelling Intravenous Oxygenator (IVOX) Device in Sheep
- Degradation Rate of Hydrocarbon by Activated Sludge in the Low Concentration Range
- A Pole-on Bipolar Outflow from the AGB Star WX Piscium
- Regulation of Plasma and Liver Total Cholesterol Levels by Dietary Oleic Acid in Rats Fed a High-Cholesterol Diet
- Finding Useful Detours in Geographical Databases
- Dynamic Orthogonal Segment Intersection Search and Its Applications(GRAPH THEORY AND APPLICATIONS)
- Effect of Oxygen Tension on Citric Acid Production by Surface Culture
- Effect of Operational Conditions on the Rate of Citric Acid Production by Rotating Disk Contactor Using Aspergillus niger
- Effects of Trypsin-Digested Outer-Arm Dynein Fragments on the Velocity of Microtubule Sliding in Elastase-Digested Flagellar Axonemes
- Proof for the Equivalence between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees
- Counting the Number of Paths in a Graph via BDDs (Special Section on Discrete Mathematics and Its Applications)
- Computational Investigations of All-Terminal Network Reliability via BDDs (Special Section on Discrete Mathematics and Its Applications)
- Potassium Removal Accompanied by Enhanced Biological Phosphate Removal
- VLBI Astrometry of the Semiregular Variable RX Bootis
- H_2O Maser Motions and the Distance of the Star-Forming Region G 192.16-3.84
- Measurement of the Distance and Proper Motions of the H_2O Masers in the Young Planetary Nebula K 3-35
- Annual Parallax Distance and Kinematical Property of H_2O Masers in IRAS 19312+1950
- How can the Web help Wikipedia? A Study of Information Complementation of Wikipedia by the Web
- Re-ranking Content Based Social Image Search Results by Multi Modal Relevance Feedback
- A Case of HELLP Syndrome with Multiple Complications
- Mining and Explaining Relationships in Wikipedia
- Computational Geometry and Linear Programming(Computational Geometry and Discrete Geometry)
- Optimization by Smoothed Bandpass Calibration in Radio Spectroscopy
- Mining Knowledge on Relationships between Objects from the Web
- Postoperative left ventricular function in patients with mitral stenosis. The effect of commissurotomy and valve replacement on left ventricular systolic function.:The Effect of Commissurotomy and Valve Replacement on Left Ventricular Systolic Function
- Flow characteristics of downflow bubble columns with gas entrainment by a liquid jet.
- GENERALIZED EQUATION OF CONTINUITY AND ITS APPLICATIONS TO HETEROGENEOUS SYSTEMS
- Annual Parallax of the K-Type Star System IRAS22480+6002 Measured with VERA
- Clinical and radiographic evaluation of total hip arthroplasties using porous tantalum modular acetabular components : 5-year follow-up of clinical trial