Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
スポンサーリンク
概要
- 論文の詳細を見る
Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number △(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate △(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by Q_N and D_N respectively, we show, among others, that △(t, Q_N)=O(tNlog((logN)/t+log2e)) for any t and N (t≧2), and △(1, D_N)=N/2 for N even.
- 社団法人電子情報通信学会の論文
- 1996-08-25
著者
-
Yamamoto Koji
Department of Internal Medicine, Hattori Memorial Hospital
-
Yamada T
Tokyo Inst. Technol. Tokyo Jpn
-
UENO Shuichi
Department of Communication and Integrated Systems, Tokyo Institute of Technology
-
YAMADA Toshinori
Department of Physical Electronics, Tokyo Institute of Technology
-
Yamada Toshinori
Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Yamada Toshinori
Department Of Applied Chemistry Institute Of Colloid And Interface Science Science University Of Tok
-
Ueno Shuichi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
-
Ueno Shuichi
Department Of Biological Science Faculty Of Science Yamaguchi University
関連論文
- Long-Term Suppressive Effect of Octreotide on Progression of Metastatic Gastrinoma with Multiple Endocrine Neoplasia Type 1: Seven-Year Follow up
- Pneumatosis Cystoides Intestinalis Induced by the Alpha-glucosidase Inhibitor Miglitol
- Stress-induced PAI-1 expression is suppressed by pitavastatin in vivo
- Analysis of Expression Profiles of Islet-associated Transcription and Growth Factors During β-Cell Neogenesis from Duct Cells in Partially Duct-ligated Mice
- β Cell Neogenesis from Ducts and Phenotypic Conversion of Residual Islet Cells in the Adult Pancreas of Glucose Intolerant Mice Induced by Selective Alloxan Perfusion
- Overexpression of the Aldose Reductase Gene Induces Apoptosis in Pancreatic β-Cells by Causing a Redox Imbalance
- Identification of amino acid residues responsible for von Willebrand factor binding to sulfatide by charged-to-alanine-scanning mutagenesis
- Immunohistochemical Localization of Betacellulin a New Member of the EGF Family in Normal Human Pancreas and lslet Tumor Cells
- Safety and Efficacy of Autologous Progenitor Cell Transplantation for Therapeutic Angiogenesis in Patients With Critical Limb Ischemia
- Recurrent Intramural Hematoma of the Small Intestine in a Severe Hemophilia A Patient with a High Titer of Factor VIII Inhibitor : A Case Report and Review of the Literature
- Liquid Phase Epitaxial Growth of High-Quality GaInAsSb/InAs
- Clinical Protocol for Angiogenesis by Intramyocardial Injection of Autologous Bone Marrow Mononuclear Cells in Patients With Severe Coronary Artery Disease : TACT-NAGOYA-HEART
- Effect of Growth Interruption during GaAs/AlGaAs Molecular Beam Epitaxy on (411)A Substrates
- Flattening Transition 0n GaAs (411)A Surfaces Observed by Scanning Tunneling Microseopy
- Therapeutic Angiogenesis by Autologous Bone Marrow Cell Transplantation : Limited Efficacy in Patients with Long-term Hemodialysis(Angiogenesis 5 (M), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- COLONOSCOPIC EXTIRPATION OF WHIPWORMS IN PATIENT WITH ACUTE ABDOMEN-LIKE SYMPTOMS
- A Case of Penetration of the Large Intestinal Wall by a Toothpick
- A Case of a Giant Lipoma of the Duodenal Bulb
- Formation of Filamentous Appendages by Acinetobacter sp. Tol 5 for Adhering to Solid Surfaces(MICROBIAL PHYSIOLOGY AND BIOTECHNOLOGY)
- Intravenous Three-dimensional CT Portography Using Multi-detector Row CT in Patients with Hepatic Cirrhosis : Evaluation of Scan Timing and Image Quality
- Syntheses of Novel Cyclotriveratrylenophane Capsules and Their Supramolecular Complexes of Fullerenes
- Syntheses of Novel Fullerene Tweezers and Their Supramolecular Inclusion Complex of C_
- Supramolucular Inclusion Complexes of Fullerenes Using Cyclotriveratrylene Derivatives with Aromatic Pendants
- Carbon δ-Doping in GaAs by Metal-Organic Molecular Beam Epitaxy
- Structural Aspects of Heavily Carbon-Doped GaAs Grown by Metalorganic Molecular Beam Epitaxy (MOMBE)
- GaAs Pseudo-Heterojunction Bipolar Transistor with a Heavily Carbon-Doped Base
- P-Type Carbon-Doped InGaAs Grown by Metalorganic Molecular Beam Epitaxy
- GaAs PN Diodes with Heavily Carbon-Doped P-Type GaAs Grown by MOMBE
- Heavily Carbon-Doped P-Type InGaAs Grown by Metalorganic Molecular Beam Epitaxy
- Superbright Green InGaN Single-Quantum-Well-Structure Light-Emitting Diodes
- Effect of Heavy Doping on Band Gap and Minority Carrier Transport of AlGaAs/GaAs HBT's (SOLID STATE DEVICES AND MATERIALS 1)
- OE-350 Drug Eluting Stent Suppressed the Elevation of Plasma Levels of MCP-1 and IL-8 in the Early Period after PCI(Restenosis basic/clinical-1, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- Reliability of Plasma Brain Natriuretic Peptide Concentration as a Surrogate Endpoint : Is it Stable in Stable Patients?(Heart Failure, Clinical 11 (M), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Strength Improvement on an Imaginary SiC Fiber of Ideal Diameter and Reduced Internal Defects Estimated from the Weibull Scaling of Tyranno ZMI Fiber(Recent Advances in Materials and Processing [II])
- Extract of Cassia nomame has effect on the cell cycle of CHO-K1 cells and suppresses chromosome aberrations induced by Mitomycin C
- 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
- Synthesis of Superconducting T'-(La_Ce_x)_2CuO_4
- Preparation and Superconducting Properties of La_(Ca_Sr_y)_Cu_2O_
- Crystal Structure of Low Oxygen-Defect Tetragonal Ba_2YCu_3O_
- Crystal Structure and Superconducting Properties of BaPb_Bi_xCu_yO_
- Facilitated Transport of Carbohydrates Across an Anion-exchange Membrane Fixed with Borate Ion
- 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
- All-Optical Inverter Operating up to 850℃ in an Erbium-Doped Phosphate Glass
- Temperature Dependence of Negative Nonlinear Absorption Effect in an Erbium-doped Borate Glass
- 50 nm Pattern Etching of Si Wafer by Synchrotron Radiation Excited CF_4 Plasma
- Electrical Properties of Al/Al_2O_3/(Ba,Rb)BiO_3/SrTiO_3(Nb) Three Terminal Device
- Sub-100nm Lithography with Using Pulsed Plasma Graft-polymerized Styrene and E-Beam Excited Plasma
- Electrical Properties of Al/Al_2O_3/(Ba,Rb)BiO_3/SrTiO_3(Nb) Three Terminal Device
- Measurement of Surface Fermi Level in Phosphidized GaAs
- Evidence for Phosphorus Passivation of Plasma-Induced Damage at GaAs Surface Probed by EL2 Traps
- Synthesis and Properties of Head-to-head,Head-to-tail,and Tail-to-tail Orientational Isomers of Extended Dihexylbithiophene-Octaethylporphyrin System [OEP-(DHBT)_n-OEP] Connected with 1,3-Butadiyne Linkages
- Involvemtnt of Ammonia Maintenance of Cytosolic Glutamine Synthetase Activity in Pisum sativum Nodules
- OE-136 Predictors of Responders in Therapeutic Angiogenesis Using Bone Marrow Mononuclear Cell Transplantation (TACT) for Critical Limb Ischemia(Peripheral circulation-1 (H) OE23,Oral Presentation (English),The 70th Anniversary Annual Scientific Meeting o
- PJ-726 Factors Associated with Urinary Excretion of Albumin in Patients with Essential Hypertension(PJ122,Hypertension, Clinical 3 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- PJ-596 Endothelial Dysfunction is a Potential Mechanism for Cardio-Renal Connection(PJ100,Kidney/Renal Circulation/CKD 5 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- Optimum Practical Design of Distributed and Asynchronous Power Control for Wireless Networks with Shared Bands(Multi-dimensional Mobile Information Networks)
- Synthesis and Structural and Electronic Properties of the Mixed Complexes of Vinylene-Bridged Bis- and Tris(octaethylporphyrin)s with Ni(II), Pd(II), and Pt(II) Ions
- An Attempted Synthesis of [7][7]Circulene: Synthesis and Characterization of Triple-Layered [2.2]Phenanthreno[2.2]naphthalenophenanthrenophane
- Ar Ion Laser-Assisted Metalorganic Molecular Beam Epitaxy of InGaAsP
- High-Performance 1.5-μm Distributed Feed Back Lasers with Strained Multi-Quantum Well Structure Grown by Metalorganic Molecular Beam Epitaxy (Chemical Beam Epitaxy)
- Low-Threshold InGaAs/ InGaAsP Multiple Quantum Well Lasers Grown by Chemical Beam Epitaxy
- Selective Area Growth of InP and InGaAs Layers on SiO_2-Masked Substrate by Chemical Beam Epitaxy
- In_Ga_As/InP Mutiquantum Well Lasers Grown by Metalorganic Molecular beam Epitaxy (MOMBE)
- Ar Ion Laser-Assisted Metalorganic Molecular Beam Epitaxy of InGaAs
- The Synthesis of a [13][15]Fulvalene Derivative
- Proapoptotic Action of p53-Tom5 in p53-Resistant A549 Human Non-small Cell Lung Cancer Cells through Direct Mitochondrial Dysfunction
- Asymmetric Ultrasonic Pulse Radiation Using Electromagnetic-Induction Transducer and PZT(Pb(Zr-Ti)O_3) Transducer with Wave Synthesis Method
- The Suppressing Effect of the Extract from Cassia nomame on Clastogenicity and Cytotoxicity of Mitomycin C in CHO Cells
- Osmotic and Non-osmotic Induction of Somatic Embryogenesis by Sucrose at High Concentrations in Daucus carota L
- Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Effects of Graded Levels of Dietary Casein and Corn Oil on Total Cholesterol and Triacylglycerol in Plasma and Liver of Rats
- Reactions of Sulfoxides with Magnesium Amides.Transformation of Sulfoxdies into Sulfides, Dithioacetals, and Vinyl Sulfides
- Nuclear localization of alkaline phosphatase in cultured human cancer cells
- Synthesis and Properties of Nucleic Acid Analogues with Peptide Backbone
- Micro-feeding of a fine powder using a vibrating capillary tube
- Synthesis and Characterization of Hepta [5] [5] circulene as a Subunit of C_ Fullerene
- Generation of transgenic mice for conditional overexpression of Sox9
- Etching of Thermally Grown SiO_2 by NH_4OH in Mixture of NH_4OH and H_2O_2 Cleaning Solution
- A novel technique for impaction bone grafting in acetabular reconstruction of revision total hip arthroplasty using an ex vivo compaction device
- Clinical significance of serum adiponectin in Japanese diabetic patients
- Long-term Efficacy of Trilostane for Cushings Syndrome due to Adrenocorticotropin-Independent Bilateral Macronodular Adrenocortical Hyperplasia
- Cemented total hip arthroplasty with subtrochanteric femoral shortening transverse osteotomy for severely dislocated hips : outcome with a 3- to 10-year follow-up period
- Thyroid Follicular Adenoma Producing Parathyroid Hormone-related Protein with a Normal Serum Calcium Level
- Relationship between serum cystatin C and serum adiponectin level in type 2 diabetic patients
- A case of mitochondrial kidney disease with insulin resistance and hypoadiponectinemia
- A Case of the Kugelberg-Welander Syndrome Complicated with Cardiac Lesions
- Resolution of Gelatinous Bone Marrow Transformation Following Hormone Replacement Therapy in a Patient with Primary Insufficiency of the Adrenal and Thyroid Glands
- Absolute configurations of novel axially dissymmetric 10,10'-dihydroxy-9,9'-biphenanthryl and its related compounds.
- Hindered Rotation in [12]Paracyclophanes
- Effective Parameter Method in Space-Dependent Neutron Slowing Down Problem
- Effective Parameter Method in Time-Dependent Neutron Slowing Down Problem
- INTRACELLULAR COLLAGEN FIBERS OF FIBROBLASTS IN THE POSTNATAL RABBIT UMBILICAL VEINS
- Synthesis of 6-O-acyl derivatives of immunoadjuvant active N-acetylmuramyl-L-alanyl-D-isoglutamine.