The MathNet Korea
Information Center for Mathematical Science

### 논문검색

Information Center for Mathematical Science

#### 논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\mathcal{NP}$-Complete

Pages. 274-287
Abstract 1. Introduction 2. Interval placement problem 3. Construction 3.1. Occurrence of a variable 3.2. Variable 3.3. Clause 3.4. Boolean formula 3.5. The weight of the first interval of a row 3.6. The weights of the clause-connecting intervals 3.7. Minimum value and $\mathcal{NP}$-completeness 4. Extensions and further results 4.1. Unweighted case 4.2. Maximization 4.3. Arbitrary width 4.4. Graph coloring 5. Application to VLSI routing 6. Conclusions single row routing, VLSI, $\mathcal{NP}$-complete problems, minimum wire length, interval graph 68Q25, 68Q35