On the complexity of three-dimensional orthogonal face routing (回路とシステム)

概要

論文の詳細を見る
The 3-D switchbox routing is a fundamental problem on the physical design of 3-D integrated circuits. The 3-D channel is a 3-D grid G and the terminals are vertices of G located in the faces of the 3-D channel. A net is a set of terminals to be connected. The objective of the 3-D switchbox routing problem is to connect the terminals in each net with a Steiner tree (wire) in G in such a way that wires for distinct nets are disjoint. The 3-D orthogonal face routing is a special case of the 3-D switchbox routing such that every terminal is located on a pair of orthogonal faces. This paper shows that the 3-D orthogonal face routing is intractable even though every net has terminals both on the orthogonal faces.
2010-11-11

著者

Ueno Shuichi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
Tayu Satoshi
Department Of Communication And Integrated Systems Tokyo Institute Of Technology
Ueno Shuichi
Department Of Biological Science Faculty Of Science Yamaguchi University

関連論文

A Note on Two Problems of Nano-PLA Design
A Note on Two Problems of Nano-PLA Design
A Note on Two Problems of Nano-PLA Design
Gene expression profiling of human myocardium with atrial fibrillation by DNA microarray analysis
Cardioprotective effects of angiotensin II receptor blockade on the molecular responses induced by mechanical stress in cardiac myocytes
DNA microarray analysis of the in vivo progression mechanism for heart failure in Dahl salt-sensitive rats
On the Complexity of Fault Testing for Reversible Circuits
A-1-26 On the Complexity of Fault Testing for Reversible Circuits
Analytical Device Model of SOI MOSFETs Including Self-Heating Effect
On Dynamic Fault Tolerance for WSI Networks
Orthogonal ray graphs and nano-PLA design (コンカレント工学)
Orthogonal ray graphs and nano-PLA design (回路とシステム)
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On Orthogonal Ray Graphs with Applications to NanoPLA Design : Extended Abstract
On the permutation routing in all-optical caterpillar networks (回路とシステム)
On the permutation routing in all-optical caterpillar networks (コンカレント工学)
On the Complexity of Three-Dimensional Orthogonal Face Routing
On the complexity of three-dimensional orthogonal face routing (回路とシステム)
On the Three-Dimensional Orthogonal Drawing of Series-Parallel Graphs
A-1-27 On the Three-Dimensional Layout of Butterfly Networks
A-1-31 A Note on Sparse Networks Tolerating Random Faults for Cycles(A-1. 回路とシステム, 基礎・境界)
On the Proper-Path-Decomposition of Trees
Fault-Tolerant Graphs for Hypercubes and Tori (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
Midblastula transition (MBT) of the cell cycles in the yolk and pigment granule-free translucent blastomeres obtained from centrifuged Xenopus embryos
ESTABLISHMENT A METHOD TO ANALYZE CELL CYCLE AND CELL DIFFERENTIATION UPON EARLY XENOPUS DEVELOPMENT USING TRANSPARENT BLASTOMERES(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
CHANGES IN INTRACELLULAR CA^ CONCENTRATION DURING EARLY EMBRYONIC CELL CYCLES IN XENOPUS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
THE REGULATING MECHANISM OF CENTROSOME SEPARATION AFTER MID-BLASTULA TRANSITION (MBT) IN XENOPUS EMBRYOS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 76^ Annual Meeting of the Zoological Society of Japan)
FUNCTIONAL ANALYSIS OF PTEN AT GASTRULATION OF XENOPUS LAEVIS(Developmental Biology,Abstracts of papers presented at the 75^ Annual Meeting of the Zoological Society of Japan)
On-Line Multicasting in All-Optical Networks
A-1-25 On Efficient Universal Quantum Circuits
Universal test sets for reversible circuits (コンカレント工学)
Universal test sets for reversible circuits (回路とシステム)
A-1-14 Fault Testing for Linear Reversible Circuits
On Fault Testing for Reversible Circuits
Expression of Matrix Metalloproteinases in Patients With Acute Myocardial Infarction
A Note on the Circuit-switched Fixed Routing in Networks (特集並列処理)
AS-1-2 Lower Bounds for the Height of Three-Dimensional Channel Routing
On Two Problems of Nano-PLA Design
On the energy-aware mapping for NoCs (回路とシステム)
A-1-21 A Note on the Three-Dimensional Single-Active-Layer Routing
A-1-30 On the Three-Dimensional Single-Active-Layer Routing with Dual Channels
A-1-13 Universal Reversible Circuits
A-1-7 On the Complexity of Three-Dimensional Orthogonal Face Routing
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the Three-Dimensional Orthogonal Drawing of Outerplanar Graphs : Extended Abstract
On the three-dimensional single-active-layer routing (回路とシステム)
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
An Efficient Quantum Addition Circuit : Extended Abstract
On the three-dimensional single-active-layer routing (コンカレント工学)
A-1-32 A Note on Fault Testing for Reversible Circuits
Special Section on Discrete Mathematics and Its Applications
Efficient Embeddings of Binary Trees with Bounded Proper Pathwidth into Paths and Grids
The Complexity of Three-Dimensional Channel Routing
AS-1-3 Three-Dimensional Channel Routing is in NP
A-1-30 A Note on the Three-Dimensional Channel Routing(A-1. 回路とシステム, 基礎・境界)
The Complexity of Three-Dimensional Channel Routing
A-1-20 On the Quantum Query Complexity of All-Pairs Shortest Paths
The Complexity of Three-Dimensional Channel Routing
AS-1-4 On the Three-Dimensional Layout of Hypercubes
AS-1-1 The Complexity of Fault Testing for Reversible Circuits
A-7-1 A Note on Universally Ideal Secret-Sharing Schemes
A-1-14 A Note on the Maximum Balanced Biclique Problem
A-1-13 A Note on the Subtree Isomorphism Problem
MSA: mixed stochastic algorithm for placement with larger solution space (VLSI設計技術)
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations (ディペンダブルコンピューティング)
An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations
A-1-34 On the Complexity of Energy-Aware Mapping for NoCs
On Efficient Universal Quantum Circuits (回路とシステム)
On Efficient Universal Quantum Circuits (システム数理と応用)
On Efficient Universal Quantum Circuits
On Efficient Universal Quantum Circuits
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs (信号処理)
A-1-8 A Note on Two-Directional Orthogonal Ray Graphs
A-1-7 A Note on the Cutwidth of Trees
A-1-6 A Note on the Energy-Aware Mapping for NoCs
On the Complexity of Fault Testing for Reversible Circuits
A-1-9 The Complexity of the Densest κ-Subgraph Problem for Chordal Bipartite Graphs
A-1-10 Characterizations of Orthogonal Ray Trees
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
On Minimum Feedback Vertex Sets in Graphs
A Note on the Energy-Aware Mapping for NoCs
A Note on the Energy-Aware Mapping for NoCs
On Minimum Feedback Vertex Sets in Bipartite Graphs and Degree-Constraint Graphs
On Minimum Feedback Vertex Sets in Graphs (信号処理)
On Unit Grid Intersection Graphs
On Unit Grid Intersection Graphs
On Unit Grid Intersection Graphs
On Orthogonal Ray Trees (回路とシステム)
On Unit Grid Intersection Graphs
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs
On the Complexity of Energy-Aware Mapping for NoCs
A-1-5 A Note on the Subtree Isomorphism Problem

On the complexity of three-dimensional orthogonal face routing (回路とシステム)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク