Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete

DOI10.1137/S0097539796303123zbMath0937.68055MaRDI QIDQ4268880

Tibor Szkaliczki

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

VLSIinterval graphsingle row routing\(\mathcal NP\)-complete problemsminimum wire length

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (14)

The transportation problem with conflicts ⋮ Chromatic Edge Strength of Some Multigraphs ⋮ Multicoloring trees. ⋮ Minimum sum set coloring of trees and line graphs of trees ⋮ Batch coloring of graphs ⋮ A short proof of the NP-completeness of minimum sum interval coloring ⋮ Minimum sum edge colorings of multicycles ⋮ Some polynomially solvable subcases of the detailed routing problem in VLSI design ⋮ On the approximability of time disjoint walks ⋮ On the minimum sum coloring of \(P_4\)-sparse graphs ⋮ Complexity results for minimum sum edge coloring ⋮ Sum coloring and interval graphs: A tight upper bound for the minimum number of colors ⋮ Minimum Sum Coloring of P4-sparse graphs ⋮ A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs

This page was built for publication: Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete