{"entities":{"Q1810659":{"pageid":1821401,"ns":120,"title":"Item:Q1810659","lastrevid":43343880,"modified":"2025-07-24T22:53:51Z","type":"item","id":"Q1810659","labels":{"en":{"language":"en","value":"On the span in channel assignment problems: Bounds, computing and counting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1924779"}},"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":"Q1810659$06BB1E75-1636-4405-81AD-350974B5EA51","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c80398debd0e9cf6cc6f5efb5288385815e85d49","datavalue":{"value":{"text":"On the span in channel assignment problems: Bounds, computing and counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1810659$2435A4A8-7D4A-471B-901F-E39B27B6EF9E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7bd328bd496ad2011bc8c7cfa1f7cc1907839ada","datavalue":{"value":"1014.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810659$D1DFF4DD-598C-4657-B648-6215B1E2C91A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cad817e4e2f26f31b2c4483cf695ef9450b3529e","datavalue":{"value":"10.1016/S0012-365X(02)00821-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810659$0DB35C21-EEB4-4AD6-94FE-563E064B7536","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$E3A35CD1-B0CC-472E-81F7-A5D893DBAAD9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2d0e39c696776e04b9e53093e3633112a8f4686","datavalue":{"value":{"time":"+2003-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1810659$20EEC22F-76D5-4F49-B8B3-5D1949AE7CD2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7f279f9e3d2e5f9d9ee77ae8263c2f7422ea5d9e","datavalue":{"value":"The channel assignment problem involves assigning radio channels to transmitters, using a small span of channels but without causing excessive interference. In this paper a standard model for channel assignment, called the constraint matrix model, is considered, which extends ideas of graph colouring. Given a graph \\(G=(V,E)\\) and a length \\(l(uv)\\) for each edge \\(uv\\) of \\(G\\), an assignment \\(\\varphi :V \\rightarrow \\{1,\\ldots ,t\\}\\) is called feasible if \\(|\\varphi (u)-\\varphi (v)|\\geq l(uv)\\) for each edge \\(uv\\). The least \\(t\\) for which there is a feasible assignment is called the span of the problem. Two bounds on the span, an upper bound (from a sequential assignment method) and a lower bound are derived. It is shown that an extension of the Gallai-Roy theorem on the chromatic number and orientations allows us to calculate the span in \\(O(n!)\\) steps for a graph with \\(n\\) vertices, neglecting a polynomial factor. It is proved that, if the edge-lengths are bounded, then the span may be calculated in exponential time, that is, in time \\(O(c^{n})\\) for a constant \\(c\\). Finally, counting feasible assignments and related quantities are considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$6469CCC0-D741-4FF5-ADA3-CFEEF43164E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810659$0AED85AB-4E80-48E5-B3CB-1C2BB8393D02","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bcb62afbf765dacab83e4ddb05b6080d7df22905","datavalue":{"value":"1924779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1810659$B4513EED-9EF7-4CD7-A0FD-B27BC8DA13F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d71ff41485748ce2d4eed71a2ccf63f8ea2b3c05","datavalue":{"value":"channel assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$DA1033D9-7264-4724-A232-BF0E347E2BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16853ae7c1bfa3a882941ed3aed47ab2be31e5f0","datavalue":{"value":"constraint matrix model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$10DE10B7-16B1-43B6-9321-4E812A281F42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1414e1128c6636d8171258ff28644da64226745c","datavalue":{"value":"graph colourig","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$55B1D0E5-89AC-449F-9855-7C515F40DED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"602871299fda387e5fe93a711a6b4c2b0f27d2a8","datavalue":{"value":"span","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$04602F89-19BD-43F4-A233-34B69FAC98BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716981f1d1c554a9a70eb8080d00a45d1123a87b","datavalue":{"value":"Gallai-Roy theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$D57A27DD-1E3A-4C08-AC3B-7D6060D4BC37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1810659$F9053A74-2E84-4818-A4EC-9780DBC2E2F9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$32B3B8DC-8F5A-471C-AD32-44129ECB1968","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$49F7176D-C1EE-42C8-9BC6-DE3D4CFA4AB4","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":"Q1810659$7E091935-3270-4208-A76A-4DE8E490121D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f8452767e48792d351acf5067c416d60a7b2b74","datavalue":{"value":{"entity-type":"item","numeric-id":4388899,"id":"Q4388899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$6AA84BCF-EC5A-4D32-B5DF-5739ACF06CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f4d73197bd0ef915ef52e264e8ec4ecc44e477f","datavalue":{"value":{"entity-type":"item","numeric-id":1229753,"id":"Q1229753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$F68AEF6D-1BE7-4674-8645-8C29506B9F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7efa2119d34420dd40c3e294d1965116ef0ef20","datavalue":{"value":{"entity-type":"item","numeric-id":4184859,"id":"Q4184859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$950A8699-2F74-4541-B0EB-ABBAFE8F1A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5025839aafa891eb881e6103d4b57ef771d2cf40","datavalue":{"value":{"entity-type":"item","numeric-id":1587609,"id":"Q1587609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$7D9BD183-64AB-470D-9111-44209945985F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2899ead5c9d26d6d0f55892261ff90f19f8a83c9","datavalue":{"value":{"entity-type":"item","numeric-id":4407445,"id":"Q4407445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$0F63853B-F011-4924-8AEE-A7EC7FAEB333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f4ea3fa4cd169f7c388f83826321e6249ffa6e1","datavalue":{"value":{"entity-type":"item","numeric-id":3438981,"id":"Q3438981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$A1A788E1-EE39-477A-B274-9492233533BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ec8b3c108a7e86e6226d9e099fe03cca38acdd5","datavalue":{"value":{"entity-type":"item","numeric-id":1356496,"id":"Q1356496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$4E682C6B-E1D1-44D8-B38E-60E2A7218440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d60e797a591aff28e03254604c24151affa84b1","datavalue":{"value":{"entity-type":"item","numeric-id":1961908,"id":"Q1961908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1810659$9B9BF3B5-DC7E-4D13-B881-F7DD445A7D1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"004d0275eca492518c22158335218cf3c9a1e0c4","datavalue":{"value":{"entity-type":"item","numeric-id":2460622,"id":"Q2460622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5012377cd7b249b265707a0baa5245efa3e90c2","datavalue":{"value":{"amount":"+0.9415116","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":"Q1810659$6D6A2F3B-7A67-42A0-A25C-EDD44D85B6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2cbe5bfb2c6ab43b0ad91cf81bd03fb7fc539b9","datavalue":{"value":{"entity-type":"item","numeric-id":5434411,"id":"Q5434411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9356ce54d7be98c36b82751ac77ea5417d248d5","datavalue":{"value":{"amount":"+0.91606873","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":"Q1810659$83469420-FC34-4F00-ADEC-E07B29B26520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b10f6dc3caf7eab71f52d28dbe0aaf60947cd116","datavalue":{"value":{"entity-type":"item","numeric-id":5363091,"id":"Q5363091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68fce8a70b1e8abde2eb1269c865cc6d2eb2b191","datavalue":{"value":{"amount":"+0.89240944","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":"Q1810659$B184431A-EBEA-4E2F-BD68-C7A74B0CD49A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83470a2d30c2c7e0f5003a1d374fd79e8f65be5c","datavalue":{"value":{"entity-type":"item","numeric-id":4962622,"id":"Q4962622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68fce8a70b1e8abde2eb1269c865cc6d2eb2b191","datavalue":{"value":{"amount":"+0.89240944","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":"Q1810659$C2744DC0-D3DD-4707-BB75-6533B409D07F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e93af69c25a54c541249fb95c3e8dc217c04bb41","datavalue":{"value":{"entity-type":"item","numeric-id":3701467,"id":"Q3701467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca7e745169dd2046ad4f2f72c4e099d7bc30bc74","datavalue":{"value":{"amount":"+0.8813157","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":"Q1810659$349DCFE7-5826-4DAF-AB52-AA73F5BA4846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e76b2226a27880d5004a3f0e522e9b3841d9f3a2","datavalue":{"value":{"entity-type":"item","numeric-id":5958140,"id":"Q5958140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d9697041e3b7ae287e03d735af5da26b6218be1","datavalue":{"value":{"amount":"+0.88009644","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":"Q1810659$D6C518E6-755A-429D-ABB4-9410FDF72B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efdb771128ee931266b8930e145b19bfe030d6ed","datavalue":{"value":{"entity-type":"item","numeric-id":4511237,"id":"Q4511237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d9697041e3b7ae287e03d735af5da26b6218be1","datavalue":{"value":{"amount":"+0.88009644","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":"Q1810659$E7DABAB8-CCD3-4A7C-A7E8-6497E815A9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e93c643e036002f2bf9537ab073df68515a86f57","datavalue":{"value":{"entity-type":"item","numeric-id":3171169,"id":"Q3171169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8d07ef73966af600ca5c6adb4829013d711b245","datavalue":{"value":{"amount":"+0.87868","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":"Q1810659$2E6FA6EE-FD61-4D73-8342-4C56045E7BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb41c49c06d4940d7940a0860662b62581f3be1c","datavalue":{"value":{"entity-type":"item","numeric-id":1630278,"id":"Q1630278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"464e5ded8d5bbc7c54cf4d0af26e7e1a88bb6433","datavalue":{"value":{"amount":"+0.87801135","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":"Q1810659$89518D1C-7B7A-4684-813B-C8726ADDD70E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7ee1498404006f93466bd69d3d0dda0b7ba56a2","datavalue":{"value":{"entity-type":"item","numeric-id":1417576,"id":"Q1417576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9b883e710b476198cdff591d028fd5203de8231","datavalue":{"value":{"amount":"+0.87741685","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":"Q1810659$AED5BB37-56AC-4C7E-B4F5-EA6472B9DDCA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1810659","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1810659"}}}}}