ASSIGNMENT OF INTERVALS TO PARALLEL TRACKS WITH MINIMUM TOTAL CROSS-TALK

Citation
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
ISSN journal
0916-8508
Volume
E81A
Issue
9
Year of publication
1998
Pages
1909 - 1915
Database
ISI
SICI code
0916-8508(1998)E81A:9<1909:AOITPT>2.0.ZU;2-G
Abstract
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.