Counting the Number of Paths in a Graph via BDDs (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes a unified approach by means of the binary decision diagram, BDD in short, to solve #P-hard problems of counting the number of paths between two terminals in undirected and directed graphs. Our approach provides algorithms running in O(2^<O(√<n>)>) time for typical planar graphs such as grid graphs. In fact, for any class of graphs having a good elimination ordering, this paradigm provides efficient solutions.
- 社団法人電子情報通信学会の論文
- 1997-04-25
著者
-
Imai Hiroshi
Department Of Bone And Joint Surgery Ehime University Graduate School Of Medicine
-
SEKINE Kyoko
Department of Information Science, University of Tokyo
-
Sekine Kyoko
Department Of Information Science 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
- 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
- Simultaneous Measurements of Energetic O^- Ions and O Atoms in Sputtering of Zinc Oxide Target
- On the Orthogonal $L_1$ Linear Approximation of Points
- 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
- A Case of HELLP Syndrome with Multiple Complications
- Computational Geometry and Linear Programming(Computational Geometry and Discrete Geometry)
- Optimization by Smoothed Bandpass Calibration in Radio Spectroscopy
- 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