{"entities":{"Q1090458":{"pageid":1101210,"ns":120,"title":"Item:Q1090458","lastrevid":49072294,"modified":"2026-01-06T13:33:56Z","type":"item","id":"Q1090458","labels":{"en":{"language":"en","value":"Finding the minimum bandwidth of an interval graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4007736"}},"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":"Q1090458$B92C8CA7-3447-4ED7-98E9-2AFED3915BEA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70ba9c85da710e7f89245b88b57f26a30eba9a4f","datavalue":{"value":{"text":"Finding the minimum bandwidth of an interval graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090458$C63F26E4-8F71-4CF5-AFD7-839EA6A54BE0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c4310b32fc8470dfe0e4fea629e378ec771d839","datavalue":{"value":"0621.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$1705780D-95E8-4583-A7E6-902EF9DAAD32","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81e558251483decb78904f7ccc5c7421a30ffdf1","datavalue":{"value":"10.1016/0890-5401(87)90028-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$D6D0C838-EA9A-4F39-B323-76230158E6A1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$B06C4EF1-6E22-45FF-9F8B-31391365B652","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$7BFC2647-1C60-4712-A08F-DE36E4FBF8EB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1090458$737EB9F8-F839-4A7F-B8F5-638B60F21E63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c111cbe231402d697423d1936eae2cd698d9f519","datavalue":{"value":"An assignment of unique integers to the vertices of a graph is called a linear layout. The bandwidth minimization problem (BANDWIDTH) is the following: Given a graph \\(G=(V,E)\\) and an integer k, determine whether there exists a linear layout of G such that the maximum difference between adjacent vertices is bounded by k. Interval graphs are the intersection graphs of a family of intervals of the real line. BANDWIDTH remains NP-complete even when restricted to special subclasses of trees. We show that BANDWIDTH can be solved in time \\(O(n^ 2)\\) for interval graphs. Moreover, for a given interval graph a linear layout with minimum bandwidth can be constructed in time \\(O(n^ 2\\log n)\\). As a by-product we get that this construction can be done for proper interval graphs in time O(n log n\\(+m)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090458$F7027911-ECA1-4164-92C8-0D5F547F2DD6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$535950AE-E4AF-48A7-9884-067500DB66AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$AA0B9D86-EF06-482B-95A5-43BBA8030B97","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"197e76d2b3050835e546a7be90e6483d2b036f46","datavalue":{"value":"4007736","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$B1D06A2C-8E05-409E-B445-DAB5EF3C5762","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e9b546562afba9bfeebc045b4015b20a62d228a","datavalue":{"value":"linear layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090458$F86262CF-64BA-4901-BA45-1FD0AA547BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc2c9c79492abbfdfb71d2529f61243ac0d03efb","datavalue":{"value":"bandwidth minimization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090458$A6BD64AA-D130-45A7-B934-AF3CE04C3200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7f0b34ec7b4e8e7ffae7da8c947e16d9f57f3a4","datavalue":{"value":"Interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090458$3E63BD9E-5EA1-4E48-B0F4-2E25D1CCF66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a7f128a8890c1ed831720a74faec8d6c0dd504e","datavalue":{"value":"NP- complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090458$AABCC4FF-7863-4CA2-AE07-0F341E86FE86","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":"Q1090458$51099E0A-510A-4D5D-9A3E-3A962C8230B9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5afafbe8e7ea3b366227baecb7bb70b76db625b4","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90028-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1090458$329ECDA3-5208-4BD6-9B64-A02E94AC737E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"121af4fe24b9adfa41c45deadd1922c97a008a88","datavalue":{"value":"W1992988744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090458$C709CC54-3277-4C98-8537-1B96B9EF9409","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb11b9dc398919e8ac3a413c7699872415247f94","datavalue":{"value":{"entity-type":"item","numeric-id":3956996,"id":"Q3956996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$6EF8553B-AAA7-4E85-A2D5-B7D077D113D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$47AB6EA4-EB8E-422B-B82B-4B0C581C368E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ba8beca23cdaad0ac4c8fdb9394466e17ade7f","datavalue":{"value":{"entity-type":"item","numeric-id":1051004,"id":"Q1051004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$0529F8E7-587A-4DD4-837C-1A420D38BCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$B1F0075E-CCFB-4DD8-B788-5A43EBF3C18D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$EBD3D7C9-8BA8-4A29-A2FE-DDE586D0CD5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e624126070d764c7d1c093d99e92a2357ea010b0","datavalue":{"value":{"entity-type":"item","numeric-id":1219893,"id":"Q1219893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$B95E8FA6-EFB8-425E-B24B-8571E9A0F86D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$240930DB-DCAD-4BDE-BDDE-00C92732E129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$821048CD-A01E-4748-AA91-3A8762EBCB0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd01152085dc6c923faefae39879822e508a915","datavalue":{"value":{"entity-type":"item","numeric-id":3219762,"id":"Q3219762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$38F4A5FC-AFC9-44C4-B9EB-417AA0F73919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$F3EE1C81-6233-4411-AB58-6814CD62D413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fddf78676d43f688f22d0ab9603f5b22b0a030","datavalue":{"value":{"entity-type":"item","numeric-id":1066674,"id":"Q1066674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$A00E1168-157E-450D-8A33-CD0ACB66EAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd6675c6fd35aca2112b944a189a93b533f77ae","datavalue":{"value":{"entity-type":"item","numeric-id":5903156,"id":"Q5903156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$F3A70F13-85F2-4BAC-AE1B-6EBD94C56B43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$D45D6CE6-7A50-4998-8B16-B392016375B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$3A7A0C52-ABDE-4F95-9F6C-2B127BC0FE44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f4aba8e0ee3a2966b3de817d74f8875ab291ae","datavalue":{"value":{"entity-type":"item","numeric-id":1223124,"id":"Q1223124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$0B76A0D2-703A-43A5-A743-2D3B298C9798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2520ef212a371adad072bb863e47e3fe5bae34e","datavalue":{"value":{"entity-type":"item","numeric-id":3960121,"id":"Q3960121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090458$90B1911B-77B4-47F0-BB5E-6442E0F33D15","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62371db6ad60de2b4c3964c834b2465674919e54","datavalue":{"value":{"entity-type":"item","numeric-id":3741647,"id":"Q3741647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3712edbcf9590d3cd9860620cbc82cac1b8ee35b","datavalue":{"value":{"amount":"+0.9927589297294616","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":"Q1090458$D54A030E-A9AB-4D98-9AB0-9EF619904A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a7c7d912199d139108eec7c19e7577237f7a21a","datavalue":{"value":{"entity-type":"item","numeric-id":3483315,"id":"Q3483315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"344e9b43a47d49ca92bc0a5ad9a81afccc0d2a97","datavalue":{"value":{"amount":"+0.8744120001792908","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":"Q1090458$63CFA745-6AC1-4D8B-B574-E4E5E143BAA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41e125597815f529b66a24918df2dc6806e5ef57","datavalue":{"value":{"entity-type":"item","numeric-id":3807243,"id":"Q3807243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdbf3f4999518f1d9a70be28f6f215818a5e593d","datavalue":{"value":{"amount":"+0.8732165098190308","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":"Q1090458$03215388-E9E3-491D-B82E-475C4EAF9D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c1d09a27526230825e34aafd1202b22dc6327a2","datavalue":{"value":{"entity-type":"item","numeric-id":1183610,"id":"Q1183610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a70956984c09e6e2fd015838f57ada2f83c170b","datavalue":{"value":{"amount":"+0.8620691299438477","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":"Q1090458$65F3C002-0587-423A-8BD8-786FA110D345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e306de382b944630c166d52acad0fb67d242bdf","datavalue":{"value":{"entity-type":"item","numeric-id":3597883,"id":"Q3597883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1a31c69aa54967986d1e4de0052e0a625c3abb","datavalue":{"value":{"amount":"+0.8618265390396118","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":"Q1090458$AD7A9DBE-3C4F-4E93-A16D-CC011FDE7E69","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1090458","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1090458"}}}}}