{"entities":{"Q1179200":{"pageid":1189949,"ns":120,"title":"Item:Q1179200","lastrevid":69811821,"modified":"2026-04-13T09:33:24Z","type":"item","id":"Q1179200","labels":{"en":{"language":"en","value":"Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 24120"}},"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":"Q1179200$1C818819-9CA2-48E0-A322-BF9C2C3F6599","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d7d2b5fe578e66810a8beb9ea88d4deacfba95a2","datavalue":{"value":{"text":"Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179200$73D4E92D-65CC-4729-925A-D6F04E059FF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2097a05676c8626081a8471f31d5eef31c5ba166","datavalue":{"value":"0747.90098","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$600828C9-A2B7-48DD-A146-81768C726522","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c444458c6c58a72e12e7c13466c21635836b83bf","datavalue":{"value":"10.1016/0377-2217(91)90254-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$8EE9AF9A-5E64-4791-AB7F-75C87F624ACF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c60e77f1a83b0d29609e088806e4dfb0721d308d","datavalue":{"value":{"entity-type":"item","numeric-id":440963,"id":"Q440963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$E1A88EAD-E46A-40D7-82DE-FEB04F4F6865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"69fdf02331b3d34bf4c6a62091878e50be512c15","datavalue":{"value":{"entity-type":"item","numeric-id":1179199,"id":"Q1179199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$02FFF523-04D0-452D-9B80-2FEB7EB910CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$7780B1EF-063E-486B-8F34-A613188F3C43","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179200$B4EC5DAB-0868-4D47-94E5-5F082B1B9E2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"154ed6ad43dee0666773d4439351d5c5c97d966b","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph associated with a weight function \\(c: V\\to\\{1,2,3,\\dots\\}\\). For a positive integer \\(k\\), an assignment of consecutive segments with distinct numbers from \\(\\{1,2,\\dots,k\\}\\) in linear order to vertices such that \\(c(v)=\\) the length of the segment for \\(v\\in V\\) and no more adjacent vertices are with the same segment is said to be an interval \\(k\\)-colouring of \\(G\\). This paper provides an exact algorithm for determining the interval chromatic number which is the smallest \\(k\\) among all interval \\(k\\)-colourings of \\(G\\) based on enumeration and the branch-and-bound principle. Further, the algorithm is used for solving the timetabling problems with lectures of different lengths.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$B70C22B0-8F5E-4ECD-86F0-21F25D9663F8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4aed06ce87e48c8c58fd5d268ea91779fe40edf","datavalue":{"value":{"entity-type":"item","numeric-id":176697,"id":"Q176697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$D9F9560D-2D15-4DC4-9D63-882951EB808F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$C3D258D2-0F40-41A2-BCC1-A48EF72E7EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$AFE2647B-9492-4D79-9934-4249D51E5625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$C7224C38-506B-4730-89B8-F6539C26E419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$7D495AC8-8C52-4A4C-95F8-4104BA0062DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$842207B7-CCDA-469A-8F5E-435D545C307E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$69735046-58BC-4996-BD48-F1C5A590D1DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$E9CAC91B-7FD8-4D2A-90C4-9EB64D658311","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fb55773f547fd7d418c75e35fdc7f952fbb75ff4","datavalue":{"value":"24120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179200$6015A864-8003-440A-942F-164A8A80E698","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"644eac1bdc796262254c6cbd203cbf6c30d985e9","datavalue":{"value":"vertex-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$D5B2C51B-1915-4A57-839D-066A9051AB2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2abc9a7a0912f14eafe2ce8fadb6f45303d13400","datavalue":{"value":"interval \\(k\\)-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$32D67EED-6662-4266-B212-7FCED32E1149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56c22d5775221423046cc5c67c2b493cdcf52842","datavalue":{"value":"exact algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$A4740750-DADA-433C-8CE0-AFB28B6A76B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60ef400fc142cd2d23aea74a064c0e2072288892","datavalue":{"value":"interval chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$552E8F8A-7748-46A7-938B-23321BA065D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25fa47f9463d515b352593e567b1400b4df9f27b","datavalue":{"value":"timetabling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179200$372A42C9-5901-4E47-BC0C-C8E874E964CE","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":"Q1179200$CB42539B-F816-4A33-9030-9174C2E04FB0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ae115cf7b2141632faa250b3688542c2c94af0d","datavalue":{"value":{"entity-type":"item","numeric-id":3832323,"id":"Q3832323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$72D6F7E6-1B0E-4B54-84B2-1C7EF155C92C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e7b26f6765114b169da5a79770389fa5bd84e12","datavalue":{"value":{"entity-type":"item","numeric-id":4175306,"id":"Q4175306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$56457695-86D4-4D74-814A-DCB9B0F86F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f330541c234741ff4f91fb0455ed22a5a58202a","datavalue":{"value":{"entity-type":"item","numeric-id":4747899,"id":"Q4747899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$934AF5C6-4FEA-42B7-956D-9CC2663428F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ab4f00910965a39e7fa4d88a7e113a6f2cca5f5","datavalue":{"value":{"entity-type":"item","numeric-id":3030582,"id":"Q3030582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$D03B4BBA-4D8A-4A93-970C-0684E94211F0","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":"Q1179200$FB90FC9F-A058-45E3-916C-0A89ADC86BF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$C0BBC48C-6EE8-4253-8CB0-E7FA78A79372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65f08e2729780cae29141db2248dcf24397815a3","datavalue":{"value":{"entity-type":"item","numeric-id":1162931,"id":"Q1162931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$BC60C9EB-A88E-44F7-AB5E-2291EEC6465B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e84d4038949f79d72c0c08a03bc29651125c7876","datavalue":{"value":{"entity-type":"item","numeric-id":5661694,"id":"Q5661694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$2AD46BC3-1C6E-43D4-9DF1-CB9B0E0CA022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb49aa8c3acf2688ebd4edb75c76cb06a79877db","datavalue":{"value":{"entity-type":"item","numeric-id":4109290,"id":"Q4109290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$9423F65F-9911-439A-AF44-2C80C4DB7B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b0e6148c6711b4917a5d908c6a1cefaaa1c6b4","datavalue":{"value":{"entity-type":"item","numeric-id":759645,"id":"Q759645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$F09629E1-0D7C-4A25-B5E4-8922FD5CB025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b928aff62d77dc50996e46297815d3e51d2cca77","datavalue":{"value":{"entity-type":"item","numeric-id":3770560,"id":"Q3770560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179200$62757F15-8113-4BC9-A215-8C2197666983","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9104d4dffb3eee2a67517ece7bea1d4b9a3f5410","datavalue":{"value":{"entity-type":"item","numeric-id":255264,"id":"Q255264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee88829cbb42b45ce5393884b41bfb26e4604a53","datavalue":{"value":{"amount":"+0.8127506375312805","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":"Q1179200$0BAC631D-8666-409B-94D4-1401D0E4CA7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca9d74597d69ad812b0dd115879ee28f3ec35e8","datavalue":{"value":{"entity-type":"item","numeric-id":2999332,"id":"Q2999332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20b06800308a3f828b1ec32a2cb699bb2ab706d0","datavalue":{"value":{"amount":"+0.8070967793464661","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":"Q1179200$AAF748F8-FE10-40CA-B135-006729D24DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ddeebd47ce3f3ebf2891b42c2ec11167250e85b","datavalue":{"value":{"entity-type":"item","numeric-id":967426,"id":"Q967426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e9a211811f4caff6496b7907fb1f54ce509c7d2","datavalue":{"value":{"amount":"+0.7985720038414001","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":"Q1179200$F4043A24-60E4-4FEC-94C8-DA53B557D34C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b693e5c887d4c07278e88877146dbabe830a675","datavalue":{"value":{"entity-type":"item","numeric-id":3059317,"id":"Q3059317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbf115876ca5f555599b43f129c1ad4370669add","datavalue":{"value":{"amount":"+0.7758278250694275","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":"Q1179200$3630387A-2846-4F06-87D9-7BAF2647E6D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bae34fb8dffc9a75f5a5002c60de0ebe92ac732","datavalue":{"value":{"entity-type":"item","numeric-id":880586,"id":"Q880586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e009ef2a5c4d02cfd1627959ef06aaeeea091fa0","datavalue":{"value":{"amount":"+0.769848644733429","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":"Q1179200$2E70EE3D-8B48-4F53-A54E-F13DC928DD33","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Exact_colouring_algorithm_for_weighted_graphs_applied_to_timetabling_problems_with_lectures_of_different_lengths"}}}}}