Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (<Special Issue>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with ★(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in ★(mn + n^2log n) time and ★(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.
- 社団法人電子情報通信学会の論文
- 2003-02-01
著者
-
Nakamura Shuji
Department Of Research And Development Nichia Chemical Industries Ltd.
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Nagamochi H
Department Of Information And Computer Sciences Toyohashi University Of Technology
-
ISHI Toshimasa
Department of Information and Computer Sciences, Toyohashi University of Technology
-
Ishi Toshimasa
Department Of Information And Computer Sciences Toyohashi University Of Technology
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
Nakamura Shuji
Department Of Cardiovascular Medicine Hiroshima University Graduate School Of Biomedical Sciences
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
-
Nakamura Shuji
Department Of Information And Computer Sciences Toyohashi University Of Technology
-
NAKAMURA Shuji
Department of Agricultural Chemistry, Faculty of Agriculture, The University of Tokyo
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- OE-175 Low-intensity Pulsed Ultrasound (LIPUS) Enhanced Angiogenesis in a Rat Hind Limb Ischemia Model, VEGF-A Expression and Mobilization in HUVEC(OE30,Preventive Medicine/Epidemiology/Education (H),Oral Presentation (English),The 73rd Annual Scientific
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- Continuous-Wave Operation of Pure Blue AlGaN-Cladding-Free Nonpolar InGaN-GaN Laser Diodes
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Antigenicity of Modified β-Lactoglobulin Examined by Three Different Assays
- Classification of Corkscrew Collaterals in Thromboangiitis Obliterans (Buerger's Disease) : Relationship Between Corkscrew Type and Prevalence of Ischemic Ulcers
- Relationship between Augmentation Index and Flow-Mediated Vasodilation in the Brachial Artery
- PE-503 Relationship between the Number of Circulating Endothelial Progenitor Cells and Medical History of Cardiovascular Diseases(Atherosclerosis, clinical(08)(IHD),Poster Session(English),The 72nd Annual Scientific Meeting of the Japanese Circulation Soc
- PE-160 Smoking Abolishes Ischemic Preconditioning-induced Augmentation of Endothelium-Dependent Vasodilation : Role of Endothelium-Derived Nitric Oxide and Endothelial Progenitor Cells(Atherosclerosis, clinical(05)(IHD),Poster Session(English),The 72nd An
- PE-118 Autologous Bone-Marrow Mesenchymal Stem Cell Implantation Induces Angiogenesis and Improves Endothelial Function in a Rabbit Ischemic Limb Model(Peripheral circulation/Vascular disease(03)(H),Poster Session(English),The 72nd Annual Scientific Meeti
- OJ-205 Aging and Hypertension Are Independent Risk Factors for Reduced Number of Circulating Endothelial Progenitor Cells(Hypertension, clinical(03)(H),Oral Presentation (Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- OE-329 Periodontitis is Associated with Endothelial Dysfunction in Healthy Subjects as Well as Hypertensive Patients(Hypertension, clinical(02)(H),Oral Presentation(English),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- Approximating a Generalization of Metric TSP(Graph Algorithms,Foundations of Computer Science)
- PJ-748 Smoking Decreases the Number of Endothelial Progenitor Cells in Healthy Subjects but not in Patients with Cardiovascular Diseases(PJ126,Smoking/Alcohol/Life Style (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circ
- PJ-723 ACE Inhibitor Imidapril versus ARB Valsaratan on Endothelial Function in Patients with Essential Hypertension(PJ121,Hypertension, Clinical 2 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- PJ-718 The Effect of Selective Mineralocorticoid Receptor Blocker Eplerenone on Endothelial Function in Patients with Essential Hypertension(PJ121,Hypertension, Clinical 2 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Ci
- PJ-665 Periodontitis, Oral Infection-Inflammatory Pathway, is a Risk Factor for Endothelial Dysfunction in Patients with Coronary Artery Disease(PJ112,Atherosclerosis (Clinical/Pathophysiology) 2 (IHD),Poster Session (Japanese),The 73rd Annual Scientific
- PJ-442 A Combination Tablet of Losartan/Hydrochlorothiazide, PREMINENT[○!R], Improves Endothelial Function in Patients with Essential Hypertension(PJ075,Hypertension, Clinical 1 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japan
- PE-424 Age and Baseline Vascular Brachial Artery Diameter are Independent Predictors of Flow-mediated Vasodilation in Healthy Subjects(PE071,Echo/Doppler (Peripheral/Vascular) (I),Poster Session (English),The 73rd Annual Scientific Meeting of the Japanese
- PE-153 Activation of Rho Kinase (ROCK) Leads to Left Ventricular Diastolic Function in Patients with Essential Hypertension(PE026,Cardiac Function (Clinical) 1 (M),Poster Session (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Soc
- OE-391 Increased Leukocyte Rho Kinase (ROCK) Activity and Endothelial Dysfunction in Cigarette Smokers(OE66,Atherosclerosis (Clinical/Pathophysiology) (IHD),Oral Presentation (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Society
- OE-340 Rho Kinase Activity is Associated with Left Ventricular Hypertrophy in Hypertensive Patients(OE58,Hypertension, Clinical 2 (H),Oral Presentation (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- Raman Scattering Studies of CuInS_2 Films Grown by RF Ion Plating
- Low-Temperature Deposition of CuIn(S_xSe_)_2 Thin Films by Ionized Cluster Beam Technique
- Approximation to the Minimum Cost Edge Installation Problem
- 510-515nm InGaN-Based Green Laser Diodes on c-Plane GaN Substrate
- High-Power Pure Blue InGaN Laser Diodes
- Superbright Green InGaN Single-Quantum-Well-Structure Light-Emitting Diodes
- High-Power InGaN-Based Violet Laser Diodes with a Fundamental Transverse Mode
- Violet InGaN/GaN/AlGaN-Based Laser Diodes Operable at 50℃ with a Fundamental Transverse Mode
- InGaN/GaN/AlGaN-Based Laser Diodes Grown on GaN Substrates with a Fundamental Transverse Mode
- Violet InGaN/GaN/AlGaN-Based Laser Diodes with an Output Power of 420 mW
- High-Power, Long-Lifetime InGaN/GaN/AlGaN-Based Laser Diodes Grown on Pure GaN Substrates
- InGaN/GaN/AlGaN-Based Laser Diodes with Modulation-Doped Strained-Layer Superlattices
- High-Power, Long-Lifetime InGaN Multi-Quantum-Well-Structure Laser Diodes
- InGaN Multi-Quantum-Well-Structure Laser Diodes with Cleaved Mirror Cavity Facets
- InGaN-Based Multi-Quantum-Well-Structure Laser Diodes
- High-Brightness InGaN Blue, Green and Yellow Light-Emitting Diodes with Quantum Well Structures
- Cd-Doped InGaN Films Grown on GaN Films
- Si-Doped InGaN Films Grown on GaN Films
- P-GaN/N-InGaN/N-GaN Double-Heterostructure Blue-Light-Emitting Diodes
- Si- and Ge-Doped GaN Films Grown with GaN Buffer Layers
- Hole Compensation Mechanism of P-Type GaN Films
- Thermal Annealing Effects on P-Type Mg-Doped GaN Films
- High-Power GaN P-N Junction Blue-Light-Emitting Diodes
- Highly P-Typed Mg-Doped GaN Films Grown with GaN Buffer Layers
- Measurement of Flow-Mediated Vasodilation of the Brachial Artery : A Comparison of Measurements in the Seated and Supine Positions
- PJ-754 Acute Administration of Caffeine Augments Endothelium-Dependent Vasodilation in Humans through an Increase in Nitric Oxide Production(Endothelium-6 (H) PJ130,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese C
- PJ-488 Relationship between Circulating Endothelial Progenitor Cells and Cardiovascular Risk(Atherosclerosis, clinical-12 (H) PJ82,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-389 The Effects of Different Intensities of Acute Exercise on Systemic and Forearm Hemodynamics in Humans : Role of Nitric Oxide(Exercise test/Cardiac rehabilitation-3 (IHD) PJ66,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting
- Pycnogenol^【○!R】, French Maritime Pine Bark Extract, Augments Endothelium-Dependent Vasodilation in Humans
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- Biexciton Luminescence from GaN Epitaxial Layers
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
- Spectral Electroluminescence Mapping of a Blue InGaN Single Quantum Well Light-Emitting Diode
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Worst Case Analysis for Pickup and Delivery Problems with Transfer
- Improvement of Crystal Quality of RF-Plasma-Assisted Molecular Beam Epitaxy Grown Ga-Polarity GaN by High-Temperature Grown AIN Multiple Intermediate Layers
- High-Quality GaN on AlN Multiple Intermediate Layer with Migration Enhanced Epitaxy by RF-Molecular Beam Epitaxy
- Structural Characterization of High-Quality ZnS Epitaxial Layers Grown on GaAs Substrates by Low-Pressure Metalorganic Chemical Vapor Deposition : Surfaces, Interfaces, and Films
- Characteristics of InGaN-Based UV/Blue/Green/Amber/Red Light-Emitting Diodes
- Current and Temperature Dependences of Electroluminescence of InGaN-Based UV/Blue/Green Light-Emitting Diodes
- Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)
- 1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization)
- 5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- 2B1 A DP-BASED HEURISTIC ALGORITHM FOR THE DISCRETE SPLIT DELIVERY VEHICLE ROUTING PROBLEM(Technical session 2B: Vehicle scheduling and communication)
- A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs(Discrete Mathematics and Its Applications)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- Comparison of Optical Properties of GaN/AlGaN and InGaN/AlGaN Single Quantum Wells
- Comparison of Optical Properties in GaN/AlGaN and InGaN/AlGaN Single Quantum Wells
- Optical Properties of an InGaN Active Layer in Ultraviolet Light Emitting Diode
- Quantum-Confined Stark Effect in an AlGaN/GaN/AlGaN Single Quantum Well Structure
- Infrared Lattice Absorption in Wurtzite GaN
- High Output Power 365nm Ultraviolet Light Emitting Diode of GaN-Free Structure : Semiconductors
- Characteristics of Ultraviolet Laser Diodes Composed of Quaternary Al_xIn_yGa_N : Semiconductors
- High-Power and Long-Lifetime InGaN Multi-Quantum-Well Laser Diodes Grown on Low-Dislocation-Density GaN Substrates
- Exciton Spectra of Cubic and Hexagonal GaN Epitaxial Films
- PE-146 Six French Transradial Approach Percutaneous Coronary Intervention with Percu Surge for Stable Angina Pectoris (SIX SENSE)(Coronary Revascularization, PTCA/Stent/DCA/Rotablator/New Device 8 (IHD) : PE25)(Poster Session (English))
- OJ-144 Impact of Persistent ST-segment Elevation after Spontaneous Reperfusion in Patients with Anterior Acute Myocardial Infarction(Acute Myocardial Infarction, Clinical (Diagnosis/Treatment) 4 (IHD) : OJ17)(Oral Presentation (Japanese))
- 5 Temporal Trend of Treatment and Outcome of Acute Myocardial Infarction(Symposium 7 (SY7) (IHD) : Longterm Prognosis of Japanese Patients with Coronary Disease : Medical Therapy, PCI, Surgical Intervention)(Special Program)
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- 292 nm AlGaN Single-Quantum Well Light Emitting Diodes Grown on Transparent AlN Base
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- Photo-Enhanced Activation of Hydrogen-Passivated Magnesium in P-Type GaN Films
- High-Quality InGaN Films Grown on GaN Films
- Clinical Implications of Obesity in Patients with Anterior Acute Myocardial Infarction
- An Approximation of the Minimum Vertex Cover in a Graph
- AlGaN-Cladding-Free m-Plane InGaN/GaN Laser Diodes with p-Type AlGaN Etch Stop Layers
- InGaN Light-Emitting Diodes with Quantum Well Structures
- Long Lifetime InGaN/GaN/AlGaN-Based Laser Diodes Grown on GaN Substrates
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)