Y. Takashima et al., ASSIGNMENT OF INTERVALS TO PARALLEL TRACKS WITH MINIMUM TOTAL CROSS-TALK, IEICE transactions on fundamentals of electronics, communications and computer science, E81A(9), 1998, pp. 1909-1915
Citations number
6
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
The most basic cross-talk minimization problem is to assign given n in
tervals to n parallel tracks where the cross-talk is defined between t
wo intervals assigned to the adjacent tracks with the amount linear to
parallel running length. This paper solves the problem for the case w
hen any pair of intervals intersects and the objective is to minimize
the sum of cross-talks. We begin the discussion with the fact that twi
ce the sum of lengths of [n/2] shortest intervals is a lower bound. Th
en an interval set that attains this lower bound is characterized with
a simple assignment algorithm. Some additional considerations provide
the minimum cross-talk for the other interval sets. The main procedur
e is to sort the intervals twice with respect to the length of left an
d right halves of intervals.