{"entities":{"Q1069442":{"pageid":1080194,"ns":120,"title":"Item:Q1069442","lastrevid":66775440,"modified":"2026-04-12T12:46:43Z","type":"item","id":"Q1069442","labels":{"en":{"language":"en","value":"An assignment algorithm with applications to integrated circuit layout"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934771"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$61201675-36C6-43E0-9589-B24161603D19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7558463f46fbadf53902951eb4eef9ca45bcd132","datavalue":{"value":{"text":"An assignment algorithm with applications to integrated circuit layout","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069442$1AAEEF52-CEAA-456C-BB65-EF1B429F174F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4c631b34fdaaab8fb3108929ef3b00a413d324e","datavalue":{"value":"0583.90066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$B728BA1B-6FBF-4CA0-9850-65EA38F93464","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"097a82271f0e791a7865552a365e660a90a98399","datavalue":{"value":"10.1016/0166-218X(86)90064-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$C1F851F6-D990-47E5-A47E-9D9145109052","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54db673cbb28bd82524949973025fcdaf1d3af32","datavalue":{"value":{"entity-type":"item","numeric-id":522962,"id":"Q522962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$7590995C-1D22-4F68-80F6-9BAEFB087193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e72a48c700caa4a7ba5a6fa38f8b3bd5b9ad1c11","datavalue":{"value":{"entity-type":"item","numeric-id":673518,"id":"Q673518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$96A06F97-BB86-4439-973E-12C4E0F38431","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$FD6C3923-9878-4911-9CCA-D01A8CC4E4AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1069442$05D5A489-EAF0-4F62-B9C2-E9568A7F1DFF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c62416fec7888c009cb39dbc0c9e76fe849ceed","datavalue":{"value":"The 2-terminal one-to-any problem, which arises in the design of layout systems, is the problem of assigning each one of n terminals positioned on the upper row of a channel (called entry terminals) to one of m terminals positioned on the lower row (called exit terminals) so that the resulting channel routing problem has minimum density. An optimal solution to this problem is known [the authors, ''On terminal assignments that minimize the density'', Techn. Report, CSD-TR-468, Purdue Univ. (1984)]. In this paper we consider a natural generalization, the 2-color one-to-any problem, in which we have two types of entry terminals, red and blue ones, and exit terminals can be assigned to either type of entry terminal. Red and blue nets created by our algorithm are allowed to run on top of each other in the routing, and the density is defined as the larger of the red density and the blue density. Its minimization is an interestig combinatorial problem. We show how to compute the best achievable density in \\(O(n+m)\\) time, and an assignment achieving this density in \\(O((n+m)\\log (n+m))\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$7DD3BAB6-9F02-4ADD-ABFB-CF49DA721C2F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$9FC3A3B9-1705-4BBC-94DC-9D9489BDD3F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$EA051674-89EC-4985-B6F2-796C67AAF79E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$D3E19188-E33A-425F-9430-7594F3562287","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dea86778bd6ce146f76a31b51fe04fa73f555abf","datavalue":{"value":"3934771","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069442$FF1EFED6-FF00-46C9-B9CB-EE278C330D10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$DBA23DB1-C23A-4326-A85C-75A29532EDA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d8de44b3f88bd19a871628a3509981cd748562","datavalue":{"value":"data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$32CBEA97-AE75-4B8E-A6C2-29CE9FBAFAAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a7bfe7dd650dba6c3ee15154eaf5ced9ae7065","datavalue":{"value":"terminal assignments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$F813EE3B-EBCF-4741-9E84-2A98AFBA65E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be914a4fec7e570b9df386a7b8fe205cc0e7937f","datavalue":{"value":"2- terminal one-to-any problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$D784FC2A-41FF-4FAB-9F3E-133A8D053405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3b41472ef781f0283d2ecdd39ab311b1a28766e","datavalue":{"value":"design of layout systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$A6C2A25C-2FC5-4FB5-99FD-E383C619E2B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52347b41d4c24216bb8529c19d2605930ed19fae","datavalue":{"value":"channel routing problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$1D5AAF22-F0C0-4075-89C9-C7649F43239A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c7118d9d996ece4a09928e052d0a5588abeb4f1","datavalue":{"value":"minimum density","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$6DB2945C-0D6C-40CB-A8E2-F592153F353E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311c918aa73c0095f25f775f111e8abd535d104e","datavalue":{"value":"optimal solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$FF668994-C983-471A-9CCB-4A98D2BAA1EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf710a88434232d69319019e9f5a0fc38b14315b","datavalue":{"value":"2-color one-to-any problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069442$7A78A6DD-BC38-4178-A2FD-D2F7F215A177","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$633C3238-069F-4484-BC79-9CBC6858A598","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$4223F563-97E8-4920-A003-A8421266612C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"134341eea2d1b7ca650bce4395810137379f40a9","datavalue":{"value":{"entity-type":"item","numeric-id":3043056,"id":"Q3043056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069442$9F759FB9-5F81-4532-AE0D-74B50CBFA642","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a433cca462ca5e195ce6b19a3ac1f540ad909022","datavalue":{"value":{"entity-type":"item","numeric-id":3997942,"id":"Q3997942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19a17ce14544ccf166531c2f6c196ffc0cfb9863","datavalue":{"value":{"amount":"+0.8967804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$7E7DC16C-AB22-40E2-BBFF-EC19568D7012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64e21a0e897ed42a13a35d2a2c6ead3644359ae3","datavalue":{"value":{"entity-type":"item","numeric-id":1124328,"id":"Q1124328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c8c5af10b97d6297673b6ce68cb6e636eaef0ad","datavalue":{"value":{"amount":"+0.8716056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$B1F410FD-BEC5-458D-9299-F633D22E0C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c645e00fe8441cefa8901ce50b4202c5c9df982","datavalue":{"value":{"entity-type":"item","numeric-id":3365340,"id":"Q3365340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eec6ab311872b3fd402e168a5540db90507fb9e","datavalue":{"value":{"amount":"+0.8690185","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$7EB20CD1-9A30-49FF-BEB1-04D8ED7F79C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1e38fe62713781391e7b57ac7074c6816dc7e12","datavalue":{"value":{"entity-type":"item","numeric-id":3321485,"id":"Q3321485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34111c90173ef7bb5988d4641e02452d3333388b","datavalue":{"value":{"amount":"+0.866854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$53B35DA7-5E03-44F7-9C2C-7472D1A1FAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e175d2b08d0aae4c0e3052a0112c4263b70c915","datavalue":{"value":{"entity-type":"item","numeric-id":3727874,"id":"Q3727874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8097be80dbda84edc605fe86eef2d1dfbaf355","datavalue":{"value":{"amount":"+0.86260164","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$8C80AF86-BD06-47B0-8550-98DC454D31D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9515549eebf607691b14ce5931c7b2b7f98f119b","datavalue":{"value":{"entity-type":"item","numeric-id":796306,"id":"Q796306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"847f22e1e68519730ae671889c34f56db52ac8c4","datavalue":{"value":{"amount":"+0.8592598","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$9038BFAD-094D-4FEA-A548-B9956409A0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f537821cdf2b4aaf6abaf3edfbfd69c43e7d799e","datavalue":{"value":{"entity-type":"item","numeric-id":3783832,"id":"Q3783832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2c2e4d3b0d79895e3672f72fc430f3ac988713","datavalue":{"value":{"amount":"+0.8583605","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$CCBF0AAC-37BE-4716-8AD9-419DA6B8CC5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"824087bb16c5bfadf07198f949d0b2d2ff964257","datavalue":{"value":{"entity-type":"item","numeric-id":5468417,"id":"Q5468417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c00250e57e682265357d7921c39431893f285107","datavalue":{"value":{"amount":"+0.85709625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$2CED3DFC-E029-4EA3-8651-B97F982F3F9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c788df73e765d28711811a664151bcbd6f782369","datavalue":{"value":{"entity-type":"item","numeric-id":3698710,"id":"Q3698710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db371f7c7e3dafbb1989997d1707bb37cba28d3d","datavalue":{"value":{"amount":"+0.8530893","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$460CDF3E-3BE0-4C8A-8939-0E4685292ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8547461bb14d08ca7fefb8b07fffacef4d83ec57","datavalue":{"value":{"entity-type":"item","numeric-id":3276894,"id":"Q3276894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41e0af66268ad4bbffc53ae4f0f1bf7dea383e25","datavalue":{"value":{"amount":"+0.8529069","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069442$9740D0C2-2DFA-4B3C-97A2-F46FDD1F9F58","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An assignment algorithm with applications to integrated circuit layout","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_assignment_algorithm_with_applications_to_integrated_circuit_layout"}}}}}