{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:05:00Z","timestamp":1740135900340,"version":"3.37.3"},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":407,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100003725","name":"Korea Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>Consider a set of nets given by horizontal segments <jats:italic>S<\/jats:italic>\u2009 = \u2009{<jats:italic>s<\/jats:italic><jats:sub>1<\/jats:sub>, \u2009<jats:italic>s<\/jats:italic><jats:sub>2<\/jats:sub>, \u2009\u2026, \u2009<jats:italic>s<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>} and a set of tracks <jats:italic>T<\/jats:italic>\u2009 = {<jats:italic>t<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>t<\/jats:italic><jats:sub>2<\/jats:sub>, \u2026, <jats:italic>t<\/jats:italic><jats:sub><jats:italic>k<\/jats:italic><\/jats:sub>} in a channel, then a track assignment consists in an assignment\nof the nets to the tracks such that no two nets assigned to the same track overlap. One\nimportant goal is to find a track assignment with the minimum number of tracks such\nthat the signal interference between nets assigned to neighboring tracks is minimized.\nThis problem is called crosstalk minimization. For a given track assignment with <jats:italic>k<\/jats:italic>\ntracks, crosstalk can be reduced by finding another track assignment for <jats:italic>S<\/jats:italic> with <jats:italic>k<\/jats:italic> tracks (<jats:italic>i.e.<\/jats:italic>, by permuting tracks). However, considering all possible permutations requires\nexponential time. For general cost function for crosstalk measure, the problem is NPhard.\nSeveral heuristic approaches were previously presented. In this paper, we consider\nspecial instances of the crosstalk\u2010minimization problem where the cost function depends\nonly on the length of the segments that runs in parallel and all pairs of segments intersect.\nAn algorithm solving this problem in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic>) time is presented. An extension\napplied to the instances with more general function of switching activity and mixed\nsignal sensitivity to reduce crosstalk and power consumption is also presented.<\/jats:p>","DOI":"10.1155\/1999\/47230","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:58:37Z","timestamp":1190120317000},"page":"87-97","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower\u2010Power and Min\u2010Crosstalk Channel Routing for Deep\u2010Submicron Layout Design"],"prefix":"10.1155","volume":"10","author":[{"given":"S. H.","family":"Nam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. D.","family":"Cho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1998,11,20]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1999\/047230.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1999\/47230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T15:17:45Z","timestamp":1723216665000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1999\/47230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,11,20]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1155\/1999\/47230"],"URL":"https:\/\/doi.org\/10.1155\/1999\/47230","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1998,11,20]]},"assertion":[{"value":"1998-09-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"1998-11-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"1998-11-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}