Polynomially Fast Parallel Algorithms for Some P-Complete Problems (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
P-complete problems seem to have no parallel algorithm which runs in polylogarithmic time using a polynomial number of processors. A P-complete problem is in the class EP (Efficient and Polynomially fast) if and only if there exists a cost optimal algorithm to solve it in T(n)=O(t(n)^ε)(ε<1) using P(n) processors such that T(n)×P(n)=O(t(n)), where t(n) is the time complexity of the fastest sequential algorithm which solves the problem. The goal of our research is to find EP parallel algorithms for some P-complete problems. In this paper first we consider the convex layers problem. We give an algorithm for computing the convex layers of a set S of n points in the plane. Let k be the number of the convex layers of S. When 1≤k≤n^<ε/2> (0≤ε≤1) our algorithm runs in O(<n log n>/p) time using p processors, where 1 ≤p≤n<1-ε>/2, and it is cost optimal. Next, we consider the envelope layers problem of a set S of n line segments in the plane. Let k be the number of the envelope layers of S. When 1≤k≤n^<ε/2>(0≤ε<1), we propose an algorithm for computing the envelope layers of S in O(<α(n)log^3n>/p) time using p processors, where 1≤p≤n<1-ε>/2, and α(n) is the functional inverse of Ackermann's function which grows extremely slowly. The computational model we use in this paper is the CREW-PRAM. Our first algorithm, for the convex layers problem, belongs to EP, and the second one, for the envelope layers problem, belongs to the class EP if a small factor of log n is ignored.
- 社団法人電子情報通信学会の論文
- 2001-05-01
著者
-
Chen Wei
Department of Obstetrics and Gynecology, Kobe University Graduate School of Medicine
-
Chen W
Mcgill Univ. Pq Can
-
Chen W
Welding Research Institute Osaka University
-
Wada K
Kawanishi Pharma Research Institute Nippon Boehringer Ingelheim Co. Ltd.
-
Wada K
Nagoya Inst. Technol. Nagoya‐shi Jpn
-
WADA KOICHI
Department of Surgery, Wada Hospital
-
WADA Koichi
Biotechnology Research Center, Toyama Prefectural University
-
CASTANHO Carla
a Ph.D. student at Nagoya Institute of Technology
-
FUJIWARA Akihiro
Department of Computer Science and Electronics, Kyushu Institute of Technology
-
Castanho C
A Ph.d. Student At Nagoya Institute Of Technology
-
Wada K
Biotechnology Research Center Toyama Prefectural University
-
Wada Koichi
Department Of Computer Science And Engineering Graduate School Of Engineering Nagoya Institute Of Te
-
Wada Koichi
The Department Of Electrical And Computer Engineering Nagoya Institute Of Technology
-
Fujiwara Akihiro
Department Of Computer Science And Electronics Kyushu Institute Of Technology
-
Chen Wei
Department Of Food And Nutrition Providence University
-
Chen Wei
The Department Of Electrical And Computer Engineering Nagoya Institute Of Technology
-
Chen Wei
Department Of Chemical Engineering Nagoya University
-
Chen Wei
Department of Electrical and Computer Engineering, Nagoya Institute Technology
-
Chen Wei
Department of Electrical and Computer Engineering, Nagoya Institute of Technology
-
Chen Wei
Department of Cell Biology, Third Military Medical University
関連論文
- Effects of progesterone receptor modulator CDB2914 on apoptosis of cultured uterine leiomyoma cells(Oncology 12)
- 7-24.Direct Effects of GnRH Antagonist (Cetrorelix) on Proliferative Activity, Apoptosis and EGF Expression in Cultured Human Uterine Leiomyoma Cells(Session 9 Others 1)
- Magnetization plateaus in one dimensional S=1/2 Heisenberg model with dimerization and quadrumerization
- Ground State Properties of One Dimensional S=1/2 Heisenberg Model with Dimerization and Quadrumerization
- SAGE library screening reveals ILT7 as a specific plasmacytoid dendritic cell marker that regulates type I IFN production
- Critical Properties of Spin-1 Antiferromagnetic Heisenberg Chains with Bond Alternation and Uniaxial Single-Ion-Type Anisotropy
- Critical Properties of Spin-1 Antiferromagnetic Heisenberg Chains with Bond Alternation and Uniaxial Single-Ion-Type Anisotropy
- Bond operator mean field approach to the magnetization plateaux in quantum antiferromagnets - Application to the S=1/2 coupled dimerized zigzag Heisenberg chains
- Magnetization plateaus in antiferromagnetic-(ferromagnetic), polymerized S=1/2 XXZ chains
- Ground State Phase Diagram of the One Dimensional S=1/2 XXZ Model with Dimerization and Quadrumerization
- Hand-assisted versus pure laparoscopic radical cystectomy : A clinical outcome comparison
- Hand-assisted laparoscopic radical cystectomy and extracorporeal urinary diversion : Experience with 31 cases
- Enzymatic Conversion of Dehydrodivanillin to Vanillin by an Anaerobic Recombinant FE7
- Anaerobic Degradation of Dehydrodiisoeugenol by Rumen Bacteria
- Polyketomycin, a New Antibiotic from Streptomyces sp. MK277-AF1 II. Structure Determination
- Polyketomycin, a New Antibiotic from Streptomyces sp. MK277-AF1 I. Taxonomy, Production, Isolation, Physico-chemical Properties and Biological Activities
- Quantitative Evaluation of the Bitterness of Commercial Medicines Using a Taste Sensor
- Preparation and Characterization of Acrylic Hydrogels Neutralized by Basic Amino Acids
- A Parallel Method for the Prefix Convex Hulls Problem
- Simultaneous Voltammetric Determination of Ascorbic Acid, Dopamine and Uric Acid Using Polybromothymol Blue Film-Modified Glassy Carbon Electrode
- A Polymer Film Modified Sensor for Voltammetric Determination of Uric Acid in the Presence of Ascorbic Acid and Its Application in Urine
- LATERAL AND AXIAL MIXING OF THE DISPERSED PARTICLES IN CFB
- Rectal carcinoid tumor associated with the Peutz-Jeghers syndrome
- Improvement in 5'-Position-selective Glucosylation of Pyridoxine by Vertidllium dahliae TPU 4900(Microbiology & Fermentation Technology)
- Polynomially Fast Parallel Algorithms for Some P-Complete Problems (Special Section on Discrete Mathematics and Its Applications)
- A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points(Special Section on Discrete Mathematics and Its Applications)
- Magnetic Neutral Loop Discharge (NLD) Plasma and Application to SiO_2 Etching Process
- Dry Etch Process in Magnetic Neutral Loop Discharge Plasma
- Parallel Algorithms for Convex Hull Problems and Their Paradigm(Special Issue on Algorithm Engineering : Surveys)
- Property of ECR Process Plasma(Physics, Process, Instrument & Measurement)
- Molecular phylogeny of species in the genera Amylostereum and Echinodontium
- Influence of Local Feature of Electron Cyclotron Resonance Plasma on the Formation of Amorphous Hydrogenated Silicon Films
- Amorphous Hydrogenated Silicon Film Deposited by Reactive Electron Cyclotron Resonance Plasma(Physics, Process, Instruments & Measurements)
- Local Structure of ECR Process Plasma
- Therapeutic potential and related signal pathway of adipose-derived stem cell transplantation for rat liver injury
- Effects of Xylooligosaccharides in Type 2 Diabetes Mellitus
- Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
- Alternative lengthening of telomeres in hTERT-inhibited laryngeal cancer cells
- Content of Selected Flavonoids in 100 Edible Vegetables and Fruits
- Band-Bending at the Graphene–SiC Interfaces: Effect of the Substrate
- Designing Efficient Parallel Algorithms with Multi-Level Divide-and-Conquer (Special Section on Discrete Mathematics and Its Applications)
- Regioselective Glucosylation of Pyridoxine by Microorganisms(Microbiology & Fermentation Technology)
- Renormalization Group Potential for Quasi-One-Dimensional Correlated Systems(Yukawa International Seminar 2004 (YKIS2004) Physics of Strongly Correlated Electron Systems)
- Finding the Envelope of Segments in Parallel
- Efficient Initialization Algorithms on Single-Hop Radio Networks(Networks)
- Special Section on Invited Papers from New Horizons in Computing
- Round Optimal Parallel Algorithms for the Convex Hull of Sorted Points (Special Section on Discrete Mathematics and Its Applications)
- A Parallel Algorithm for the Stack Breadth-First Search(Regular Section)
- Electrochemical Oxidation of Luteolin at a Glassy Carbon Electrode and Its Application in Pharmaceutical Analysis
- Derivation of Hepatocytes From Injected Bone Marrow cells in Mice After Partia Hepatectomy and D-Galactosamine Induced Hepatic Injury(THE SIXTH JAPAN-CHINA JOINT SEMINAR ON HISTOCHEMISTRY AND CYTOCHEMISTRY)
- Characterization of Rat Hair Follicle Stem Cells Selected by Vario Magnetic Activated Cell Sorting System
- Architecture and Performance of Dynamic Offloading Mechanism for Maestro2 Cluster Network
- Architecture and Performance of Dynamic Offloading Mechanism for Maestro2 Cluster Network
- Establishment of an Experimental Mouse Model of Trauma-Hemorrhagic Shock
- A Leakage-Aware CS/CB Scheme for Heterogeneous CoMP Networks with Layered Limited Feedback
- A fuzzy evaluation of schedule robustness under processing time variations in batch plants.
- Effect of the regulation of retinoid X receptor-α gene expression on rat hepatic fibrosis
- A Leakage-Aware CS/CB Scheme for Heterogeneous CoMP Networks with Layered Limited Feedback