{"entities":{"Q1853136":{"pageid":1863878,"ns":120,"title":"Item:Q1853136","lastrevid":48034174,"modified":"2026-01-03T10:36:50Z","type":"item","id":"Q1853136","labels":{"en":{"language":"en","value":"The on-line first-fit algorithm for radio frequency assignment problems."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856475"}},"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":"Q1853136$A917DABB-7294-488E-9627-D80AD1A62C6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"921b790cb998ecc319769cdc871f81bd9f02a840","datavalue":{"value":{"text":"The on-line first-fit algorithm for radio frequency assignment problems.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853136$8ED1ECE1-CDF2-4389-9FC2-70A20569DC68","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd598d3ba31f734b7601c1be85dc13c6161e81a6","datavalue":{"value":"1042.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853136$5E84BB7F-30D2-46FB-A2BA-1937C0F055DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f1c9b917932e710a43b84618c42029943089b57","datavalue":{"value":"10.1016/S0020-0190(02)00283-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853136$1CB658F1-4222-4DF9-AF7A-7B44EE4719F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"48a830cf124b00e0c6ee2c6d203f9e8c1f4f0f93","datavalue":{"value":{"entity-type":"item","numeric-id":378250,"id":"Q378250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$E2D5D6B1-794B-4EF0-B7C7-C4776A3F05BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a0548b5067becd9ad6f0d12a6e8576f634acf90","datavalue":{"value":{"entity-type":"item","numeric-id":845677,"id":"Q845677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$162F2E56-3817-47F4-B0DD-985D784C3186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"89dc842a0efd2285e441e1240844ffbee89688a3","datavalue":{"value":{"entity-type":"item","numeric-id":1607055,"id":"Q1607055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$D7B00A08-F453-4D7B-8A8E-F8384ECE153D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$4458488E-C8EE-4BBE-8B9D-6EC9014FC54C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853136$135270E7-2C58-4101-B0DA-400D75629E34","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"17936f0bc8d5cfefab600388e7745fe222378e2a","datavalue":{"value":"The radio frequency assignment problem is to minimize the number of frequencies used by transmitters with no interference in radio communication networks; it can be modeled as the minimum vertex coloring problem on unit disk graphs. In this paper, we consider the on-line first-fit algorithm for the problem and show that the competitive ratio of the algorithm for the unit disk graph \\(G\\) with \\(\\chi(G)=2\\) is 3, where \\(\\chi(G)\\) is the chromatic number of \\(G.\\) Moreover, the competitive ratio of the algorithm for the unit disk graph \\(G\\) with \\(\\chi(G)>2\\) is at least \\(4-3/\\chi(G)\\). The average performance for the algorithm is also discussed in this paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853136$6ED6FA6D-78FB-41DC-A45C-E97A5E11BDA2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853136$ADF066DA-6BBE-4C6F-BD4F-C6E4CFB54EAE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"708cdedb1ebf99b17ac91bfb90f2139ed2b1f7e3","datavalue":{"value":"1856475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853136$0F7F8774-E467-4433-A6AF-5D0C2FA060C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24e766ff1fdf717a9b0cf85479b2a8426700b399","datavalue":{"value":"Unit disk graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853136$3338B792-EB38-4A55-A3F3-51F84145AA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dbc157a636f0f706137a818b7e4104f92479ff6","datavalue":{"value":"Radio frequency assignment problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853136$995F80EF-83C4-4427-98ED-0B1E1F5E4671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd5567deb0ce2f1e174a905ea12c49711d19660d","datavalue":{"value":"Graph coloring problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853136$1FD7F877-A830-4FB7-BD19-D570E7AA055B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7bcd354d3cafd63e238f661b84335318abe3297","datavalue":{"value":"On-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853136$8F05275C-1F92-402B-9FB0-FA20715FA861","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":"Q1853136$344C1404-8F0C-42BE-B4CF-2257ADA10C3B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ba8e98804812739b2b90fbe2981ad427424080","datavalue":{"value":{"entity-type":"item","numeric-id":3128993,"id":"Q3128993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$991001F3-51D0-473A-B60F-72325A21FF36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$DAD4DD2B-B05C-4E38-B3E4-84182F09D1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0a876e959b6e1cf5ba72cd222f33874a5f0081e","datavalue":{"value":{"entity-type":"item","numeric-id":1386337,"id":"Q1386337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$B6E1935E-EBB5-4DF1-9317-42290119A5FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95f98b95de3fc63542346b5e5a52078a1b82904a","datavalue":{"value":{"entity-type":"item","numeric-id":3804717,"id":"Q3804717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$A40CDC97-F608-4BA6-AA4B-0CA6A9DA8D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89868853df043aedbe5af48c8d8f899bca136343","datavalue":{"value":{"entity-type":"item","numeric-id":5344631,"id":"Q5344631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$FD7957F1-DE0D-4CF4-9590-7E11DB58A57A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9c0a0496cac0485cd86316f1d46f4eb449c720","datavalue":{"value":{"entity-type":"item","numeric-id":1124602,"id":"Q1124602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$F1EF1FD1-5A53-43A0-9A01-AF1997519914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"798013f0207239d4ee11305fbc7314d0fa94dd8a","datavalue":{"value":{"entity-type":"item","numeric-id":3975168,"id":"Q3975168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$BA82D35E-876B-4209-9D97-81CE8785436F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8200125ef11722586c24d53c7be84aac4540e07","datavalue":{"value":{"entity-type":"item","numeric-id":4858840,"id":"Q4858840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853136$F731C65B-2F72-444F-A3F5-3D24E94F7501","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13ffecb0da8f1ce48a82a1c5cae5c0519b87f723","datavalue":{"value":{"entity-type":"item","numeric-id":4232883,"id":"Q4232883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17e2146f78c66217d668bf3041b45a62fd54c26d","datavalue":{"value":{"amount":"+0.8339516520500183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853136$8C9C98E6-D652-4632-ACD8-D057EF4E656E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49d8148d51952faf2e91f78fbc71ab4d48924a08","datavalue":{"value":{"entity-type":"item","numeric-id":5952557,"id":"Q5952557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17e2146f78c66217d668bf3041b45a62fd54c26d","datavalue":{"value":{"amount":"+0.8339516520500183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853136$B20651DC-EE50-480B-AF5F-B3E69F36AA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b32aee0020343fb8a8d3456525c35e76c0048814","datavalue":{"value":{"entity-type":"item","numeric-id":4540061,"id":"Q4540061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d43b2eb0d7845d2a609c2c6ffff3f0502cd8212b","datavalue":{"value":{"amount":"+0.803641140460968","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853136$8B0C2C31-7A1D-408E-B8A2-91D0C86FC928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f39161032708337db78732870ec97a42d1f65045","datavalue":{"value":{"entity-type":"item","numeric-id":4550766,"id":"Q4550766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a33619b5759528b12d6ff0e26ad2ad17c70f2969","datavalue":{"value":{"amount":"+0.800291121006012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853136$3DA95916-C313-4317-9B76-5C2EF4BCAD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11439f3e7a54bc3b4bcfc57b56890af3cb6eec4d","datavalue":{"value":{"entity-type":"item","numeric-id":1041229,"id":"Q1041229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a33619b5759528b12d6ff0e26ad2ad17c70f2969","datavalue":{"value":{"amount":"+0.800291121006012","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1853136$855FC442-E356-4556-B532-5B52EE28919D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1853136","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1853136"}}}}}