An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut
スポンサーリンク
概要
- 論文の詳細を見る
We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the subnetwork extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.
- 社団法人電子情報通信学会の論文
- 2001-05-01
著者
-
Kajitani Y
Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Kajitani Yoji
The Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Kajitani Yoji
Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Takahashi Atsushi
Department Of Cardiology Akita City General Hospital
-
AZEGAMI Kengo
Department of Electrical and Electronic Engineering, Tokyo Institute of Technology
-
Azegami Kengo
Department Of Electrical And Electronic Engineering Tokyo Institute Of Technology
-
Takahashi Atsushi
Departmant Of Surgery(i) Kanazawa University School Of Medicine
関連論文
- PJ-668 Incremental Value of Combined 64-Slice Computed Tomography Angiography and Stress Myocardial Perfusion Imaging for Detection of Coronary Artery Disease(CT / DSA(10)(I),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circ
- PJ-342 Rapid Progression of Coronary Artery Lesions From Mild to Severe Stenosis With Intravascular Ultrasound Virtual Histology(Intravascular endoscopy/Intravascular ultrasound(06)(I),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Jap
- PJ-229 Clinical Profiles of Rapid Progression of Coronary Artery Lesions From Mild to Severe Stenosis Within One Year(Atherosclerosis,clinical(10)(IHD),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- Hepatic Adenomatous Hyperplasia with Hyperattenuation on CT During Arterial Portography: A Case Report
- PJ-200 Depression Persists in Patients with Implantable Cardioverter Defibrillator in Long Term(PJ034,Stress-psychosomatic Medicine (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- OJ-015 Psycological distress in patients with Implantable Cardioverter Defibrillator(Autonomic nervous system(02)(H),Oral Presentation(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-235 Recovery Time Dispersion and Arrhythmic Event in Patients with Cardiac Resynchronization Therapy Device(PJ040,CRT/ICD 2 (M),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- PJ-090 The Clinical Utility of Defibrillation Waveform Optimization(PJ015,ICD (M),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- OE-280 Clinical Significance of Electrical Storm after Initiation of Cardiac Resynchronization Therapy(OE48,CRT (M),Oral Presentation (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- PJ-792 The Clinical Predictors of High Defibrillation Threshold in Implantable Cardioverter Defibrillators : Is there hint in the Chest X-ray?(Arrhythmia, therapy(22)(A),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulati
- PJ-788 Measures for the Patients with High Defibrillation Threshold and the Outcome(Arrhythmia, therapy(22)(A),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- WHAT IS ADEQUATE REVASCULARIZATION IN PATIENTS WITH LEFT MAIN CORONARY STENOSIS?
- PJ-013 Visual and Quantitative Assessment of Angiographic Myocardial Blush Grade in Acute Myocardial Infarction With Multidetector Computed Tomography(Acute myocardial infarction, clinical(diagnosis/treatment)(08)(IHD),Poster Session(Japanese),The 72nd An
- PE-513 Assessment of Myocardial Viability, Left Ventricular Remodeling and Prognosis After Acute Myocardial Infarction With 64-slice Multidetector Computed Tomography(CT/DSA(06)(I),Poster Session(English),The 72nd Annual Scientific Meeting of the Japanese
- PE-489 The Long-Term Effect of Extensive Pulmonary Vein Isolation for Paroxysmal Atrial Fibrillation. How Long Should We Follow The Patients?(Arrhythmia,therapy(10)(A),Poster Session(English),The 72nd Annual Scientific Meeting of the Japanese Circulation
- PE-488 Left Atrial Ablation Can be Safely Performed in Patients with Atrial Fibrillation and Prior Cerebral Infarction(Arrhythmia,therapy(10)(A),Poster Session(English),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- PE-060 Relationship Between Quantitative Measurements of Coronary Senosis Severity by Computed Tomography Angiography and the Physiologic Significance of Myocardial Perfusion(CT/DSA(04)(I),Poster Session(English),The 72nd Annual Scientific Meeting of the
- Retroperitoneal lymphangioma with a duodenal lesion in an adult
- Takayasu's Arteritis in a 69-year-old Woman
- A case-control study of diet and prostate cancer in Japan : possible protective effect of traditional Japanese diet
- PJ-344 Assessment of Myocardial Reperfusion by 64-slice Multidetector Computed Tomography in Patients Treated With Primary Stenting for Acute Myocardial Infarction(CT/DSA-08, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- OJ-129 Quantitative Measurements of Coronary Senosis Severity by 64-Slice Computed Tomography Angiography and the Relation to Physiologic Significance of Myocardial Perfusion(CT / DSA-04, The 71st Annual Scientific Meeting of the Japanese Circulation Soci
- WS1-2-4 Phase I Clinical Study of Anti-apoptosis Protein, Survivin-derived Peptide Vaccine Therapy for Patients with Advanced or Recurrent Urothelial Cancer(Urothelial Cell Cancer)
- Peroxisome proliferator-activated receptor gamma is frequently underexpressed in renal cell carcinoma
- Bladder cancer discovered by ovarian metastasis : Cytokeratin expression is useful when making differential diagnosis
- Cell proliferation, apoptosis, angiogenesis and growth rate of incidentally found renal cell carcinoma
- Elevated serum estradiol suggesting recurrence of Leydig cell tumor nine years after radical orchiectomy
- Does transurethral resection of the prostate facilitate detection of clinically significant prostate cancer that is missed with systematic sextant and transition zone biopsies?
- Recurrence of renal cell carcinoma more than 5 years after nephrectomy
- Growth rates of primary and metastatic lesions of renal cell carcinoma
- Recovery of sexual function after nerve-sparing radical prostatectomy or cystectomy
- Treatment for Advanced Testicular Cancer with High-Dose Chemotherapy and Autologous Blood Stem Cell Transplantation
- Routability Driven Via Assignment Method for 2-Layer Ball Grid Array Packages
- Gastrointestinal Stromal Tumor of the Lesser Omentum in a Young Adult Patient with a History of Hepatoblastoma : Report of a Case
- Whole-genome profiling of chromosomal aberrations in hepatoblastoma using high-density single-nucleotide polymorphism genotyping microarrays
- Metastatic Cervical Carcinoma Mimicking Kidney Abscess
- PE-295 Bleeding Complications Associated with Dual Antiplatelet Therapy Plus Anticoagulant in Patients who Underwent Percutaneous Coronary Intervention with Drug-Eluting Stents(Coronary revascularization,PCI(11)(IHD),Poster Session(English),The 72nd Annua
- 5 Prevention of Sudden Cardiac Death in Japanese Patients with Nonischemic Heart Failure(Heart Failure and Arrhythmia, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- Quality of life in patients having an ileal conduit, continent reservoir or orthotopic neobladder after cystectomy for bladder carcinoma
- Molecular markers for reinforcement of histological subclassification of neuroendocrine lung tumors
- OJ-069 Efficacy of Amiodarone in Prevention of Implantable Cardioveter Defibrillator Shocks in High-Risked Japanese Patients with Nonischemic Cardiomyopathy(Arrhythmia, therapy-06, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-604 Prediction of a Successful Defibrillation with a Single Low-energy Shock during Implantable Defibrillator Implantation Testing(Arrhythmia, therapy(21)(A),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Societ
- PJ-602 A Single Low-energy Shock Defibrillation Predicts a Successful ICD Lead System Configuration(Arrhythmia, therapy(21)(A),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-035 Short-term stability and pacing parameters of coronary sinus lead : Effect of defibrillation threshold test(Arrhythmia, therapy(23)(A),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- FRS-046 Renal Insufficiency and Appropriate Shock Therapy in Heart Failure Patients with Implantable Cardloverter Defibrillator(Novel Strategies for Arrhythmia(1)(A),Featured Research Session,The 72nd Annual Scientific Meeting of the Japanese Circulation
- Origin of Anomalous Optical Absorption in Double-Exchange Ferromagnet La_Sr_xMnO_3
- Nitric Oxide Derived from Human Umbilical Vein Endothelial Cells Inhibits Transendothelial Migration of Neutrophils
- Rapid and Prominent Up-Regulation of High-Affinity Receptor for Immunoglobulin G (FcγRI) by Cross-Linking of β_2 Integrins on Polymorphonuclear Leukocytes
- Increased Washout Rate of ^Tc-MIBI of Non-infarcted Myocardium in Acute Myocardial Infarction(Nuclear Cardiology 7 (I), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Prognostic Value of Combination of Early Washout Rate of ^I-MIBG Myocardial Scintigraphy and BNP in Patients with Stable Heart Failure(Nuclear Cardiology 10 (I), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Sarcomatoid transitional cell carcinoma originating from a duplicated renal pelvis
- MRI Findings in the Liver in Biliary Atresia Patients after the Kasai Operation
- 3,4-Dihydroxyphenylalanine(DOPA) Decarboxylase Deficiency and Resultant High Levels of Plasma DOPA and Dopamine in Unfavorable Neuroblastoma
- Gate-Level Register Relocation in Generalized Synchronous Framework for Clock Period Minimization(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Human-robot cooperative rope turning : an example of mechanical coordination through rhythm entrainment
- Possible Orbital Orderings in a Model of Metallic Double-Exchange Ferromagnets : Condensed Matter: Electronic Properties, etc.
- Solid-phase Extraction of High Oxidation State Metal Ion-Desferrioxamine B Chelates Using Sulfuric Acid-treated Silica Gel
- Anatomical Linear Ablation during Sinus Rhythm for Verapamil-sensitive Idiopathic Left Ventricular Tachycardia(Arrhythmia, Non-pharmacological Therapy 11 (A), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Relation Between Plasma Nitric Oxide Levels and Diabetic Retinopathy
- Non-invasive Evaluation of Endothelial Function in Retinal Microcirculation Using a Laser Doppler Velocimetry System(Endothelium/NO 1 (H), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Spontaneous Conversion and Maintenance of Sinus Rhythm by Combination Bepridil and Flecainide Therapy in Patients with Chronic Lone Atrial Fibrillation
- Combination bepridil and flecainide therapy for conversion of chronic lone atrial fibrillation
- Possible involvement of adrenomedullin in lipopolysaccharide-induced small-intestinal motility changes in conscious rats
- OE-132 New Strategy of Left Atrial Ablation for Persistent Atrial Fibrillation : Bepridil Can Lead to Appropriate Ablation Strategy(Arrhythmia, therapy(02)(A),Oral Presentation(English),The 72nd Annual Scientific Meeting of the Japanese Circulation Societ
- The effects of intestinal ischemia on colonic motility in conscious rats
- Bilateral ovarian teratomas successfully treated by ovary-conserving technique
- In vivo recording of colonic motility in conscious rats with deficiency of interstitial cells of Cajal, with special reference to the effects of nitric oxide on colonic motility
- Effect of Endotoxin on Colonic Motility in Conscious Rats
- Minimal Forbidden Minors for the Family of Graphs with Proper-Path-Width at Most Two
- Universal Graphs for Graphs with Bounded Path-Width
- On the Proper-Path-Decomposition of Trees
- Mechanical trouble with balloon and cuff of silicone catheter is still a clinical problem : little progression in uro-catheters?
- The Oct-Touched Tile : A New Architecture for Shape-Based Routing( Analog Circuit Techniques and Related Topics)
- A Device-Level Placement with Schema Based Clusters in Analog IC Layouts(Analog Layout)(VLSI Design and CAD Algorithms)
- Abstraction and Optimization of Consistent Floorplanning with Pillar Block Constraints(Floorplan)(VLSI Design and CAD Algorithms)
- Schedule-Clock-Tree Routing for Semi-Synchronous Circuits (Special Section on VLSI Design and CAD Algorithms)
- Clinical characteristics and surgical treatment of perianal and perineal rhabdomyosarcoma : analysis of Japanese patients and comparison with IRSG reports
- Phenytoin and Its Metabolite, 5-(4-Hydroxyphenyl)-5-Phenylhydantoin, Show Bone Resorption in Cultured Neonatal Mouse Calvaria
- Optimal Time-Multiplexing in Inter-FPGA Connections for Accelerating Multi-FPGA Prototyping Systems
- Computational Complexity Analysis of Set-Bin-Packing Problem(Special Section on Discrete Mathematics and Its Applications)
- Assignment of Intervals to Parallel Tracks with Minimum Total Cross-Talk
- Routability of FPGAs with Extremal Switch-Block Structures(Special Section on Discrete Mathematics and Its Applications)
- Micropatterned HeLa Cell Culture on PEG Monolayer-Coated Glass Substrates
- Systemic Sarcoidosis with Significant Granulomatous Swelling of the Pharyngeal Tonsil
- Clinical features of liver dysfunction in collagen diseases
- Ectopic Ureterocele with a Horseshoe Kidney in an Adult
- Effect of Adrenalectomy on the Substrate Interaction with Cytochrome P-450 in the Hydroxylation of Steroid Hormones by Liver Microsomes
- A Fast Clock Scheduling for Peak Power Reduction in LSI
- Minimization of Delay Insertion in Clock Period Improvement in General-Synchronous Framework
- Properties of the Pion-Pion Interaction Derived from the Analysis of Pion-Nucleon Scatterings
- Pion-Pion Interaction and Pion-Nucleon Scattering
- An Improvement of Network-Flow Based Multi-Way Circuit Partitioning Algorithm
- An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut
- Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan(Special Section on Discrete Mathematics and Its Applications)
- Kinetic Analysis for Oxidation of Oleic Acid
- レｰザｰあざ治療時に母斑より発生する音響衝撃波の基礎研究
- A High-Speed and Low-Power Clock Tree Synthesis by Dynamic Clock Scheduling(Special Section on VLSI Design and CAD Algorithms)
- A Via Assignment and Global Routing Method for 2-Layer Ball Grid Array Packages(Discrete Mathematics and Its Applications)
- Routability Driven Via Assignment and Routing for 2-Layer Ball Grid Array Packages
- シリカ/ポリビニルアルコ-ル複合体の延伸とその複合体より得られるシリカゲルの細孔構造