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
Tibor Szkaliczki,
Pages. 274-287
Abstract
Contents 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
Key words single row routing, VLSI, $\mathcal{NP}$-complete problems, minimum wire length, interval graph
Mathmatical Subject Classification 68Q25, 68Q35