The search functionality is under construction.

Keyword Search Result

[Keyword] intersecting interval sets(1hit)

1-1hit
  • Assignment of Intervals to Parallel Tracks with Minimum Total Cross-Talk

    Yasuhiro TAKASHIMA  Atsushi TAKAHASHI  Yoji KAJITANI  

     
    PAPER-VLSI Design Technology and CAD

      Vol:
    E81-A No:9
      Page(s):
    1909-1915

    The most basic cross-talk minimization problem is to assign given n intervals to n parallel tracks where the cross-talk is defined between two intervals assigned to the adjacent tracks with the amount linear to parallel running length. This paper solves the problem for the case when any pair of intervals intersects and the objective is to minimize the sum of cross-talks. We begin the discussion with the fact that twice the sum of lengths of n/2 shortest intervals is a lower bound. Then 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 procedure is to sort the intervals twice with respect to the length of left and right halves of intervals.