{"entities":{"Q1600003":{"pageid":1610743,"ns":120,"title":"Item:Q1600003","lastrevid":72299823,"modified":"2026-04-14T03:58:22Z","type":"item","id":"Q1600003","labels":{"en":{"language":"en","value":"Complexity of some special types of timetabling problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1751678"}},"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":"Q1600003$C3FA9583-A876-495F-8E4E-EFD9194129CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d602a4e0988496908404b40b01c4306e36da58dd","datavalue":{"value":{"text":"Complexity of some special types of timetabling problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1600003$B639FEFB-CDDF-4707-8EA1-867D9B69DF24","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bed83ee42208419b3d927bf39d41fcab8d77b460","datavalue":{"value":"0996.90039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$034249F0-D986-4723-8109-A7FA3BFA34A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ca85145c5bcf26b9d6b48940983710606ab54cb","datavalue":{"value":{"entity-type":"item","numeric-id":1581051,"id":"Q1581051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$3D0DCCF7-322B-431A-98C3-17EB1777CF7E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39245fc27c04eb23fa7211454c51f34f7f46a9a0","datavalue":{"value":{"entity-type":"item","numeric-id":177699,"id":"Q177699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$E0DED54D-B491-4D23-AC1A-5BE7E16D7337","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"699252fe7d0c2555c03ae79bf201a68b560e82c1","datavalue":{"value":{"time":"+2002-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1600003$4975FCE9-99DF-4CAB-82EA-2B931034942E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c6ed5e1eb98da9c6310d8e5c05fad8b1d6ea270","datavalue":{"value":"Starting from the simple class-teacher model of timetabling (where timetables correspond to edge colorings of a bipartite multigraph), the authors consider an extension defined as follows: it is assumed that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. The authors show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. It is also examined the case where there are at most two groups of classes and a polynomial procedure based on network flows to find a timetable using at most \\(t\\) periods, is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1600003$7604BE8A-786E-490B-B52D-C59CE548CC04","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"208fd2cac25388eac9d979aba68dad257ddb3873","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$4D33E14B-833F-4E99-B239-E083B95E37F5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$ED2CDDCC-1CFA-49A6-A694-C4A28630CDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$5BE7823B-E7A2-45F9-BDDE-EF2342C5F7B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfa2c51021d8f072dbbab98b52cd2a40c6f5d0d8","datavalue":{"value":"1751678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$4B3FF2C8-953C-4287-B5F7-6792CE28FDAE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1600003$BD5B9168-628B-4A25-9548-3A10BFF373A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1600003$EC8595DA-016B-4D25-8DF2-A0609E650760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25fa47f9463d515b352593e567b1400b4df9f27b","datavalue":{"value":"timetabling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1600003$0D4A25EA-ABD3-4F3E-97E3-D3EB0C81CD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1600003$63659C5F-55DB-4B87-86EA-EC5D6B31B6A0","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":"Q1600003$AEA724E6-1DD9-42D0-8174-1B660F80999D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c248d5eb2d78d58f43f72b9501429c5c5b223cc3","datavalue":{"value":"https://doi.org/10.1002/jos.97","type":"string"},"datatype":"url"},"type":"statement","id":"Q1600003$F9E85C17-1DC1-409A-9236-32B92D4AA8F4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa45e7a8d35d01ecfd9e0522e6cfc7980f8864af","datavalue":{"value":"W1984680233","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$EC892CB1-6807-4207-BAC1-A087F859CE13","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b68ec865cb7baf88f2cd7bcba9c3c7c3fbd782b","datavalue":{"value":{"entity-type":"item","numeric-id":1333322,"id":"Q1333322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$A1C24167-F181-4AF4-8E92-6CE02791C58E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77603a316f9fc5a4ef71b23813df472c259d2abf","datavalue":{"value":{"entity-type":"item","numeric-id":4208001,"id":"Q4208001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$A388CE30-9B98-42E6-A8E0-66BBA7A6B2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b93ea35164fa9388acaf3d38d04c805085a5a9","datavalue":{"value":{"entity-type":"item","numeric-id":1186309,"id":"Q1186309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$F863F520-6577-4409-AB9F-068F067E80AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a5ac2f0c9be20432bbe40d71b9c60ed74ffd46a","datavalue":{"value":{"entity-type":"item","numeric-id":1363753,"id":"Q1363753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$B97F1C48-8739-4616-B553-2C9A899635E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d3de3637f427f6f65fe0eb1b99255f0f8c30657","datavalue":{"value":{"entity-type":"item","numeric-id":1356739,"id":"Q1356739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$985DAEA7-3007-4FDC-95D7-352BDC25212D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1895e376e36bd982363114715162191404ccdeef","datavalue":{"value":{"entity-type":"item","numeric-id":1278524,"id":"Q1278524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$9B043A2C-55F7-4769-B666-B73E5A42D95E","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":"Q1600003$37C9B469-F221-4F11-8FC0-9DA5B8BAB357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76b59f2fe0b035d9f6b252635266d8c9bfd51e66","datavalue":{"value":{"entity-type":"item","numeric-id":4380372,"id":"Q4380372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$8255364E-A5BA-4836-8F23-0A93FF88921B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$54466A20-2E26-4E46-B1FA-27731DEB729D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d3405d44e153c646c49640e5f0c8b7909fc085","datavalue":{"value":{"entity-type":"item","numeric-id":1268282,"id":"Q1268282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1600003$6FAC2D1D-136C-459D-9BE7-48A11E034860","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":"Q1600003$C0155E3D-AFEC-4F3D-8C49-967ABF45659D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"169d4cbc17f83345c32f4dcd4f71ef83c0dc5db8","datavalue":{"value":"10.1002/JOS.97","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1600003$FD84EC27-1322-4CEF-A454-F1BDBEC23976","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3daff064b0f476e3a274f9327e924d1064647939","datavalue":{"value":{"entity-type":"item","numeric-id":2711272,"id":"Q2711272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1807b96ab95865a085a4a5af10d4364a97dd74a2","datavalue":{"value":{"amount":"+0.91619164","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":"Q1600003$A2BA21AC-617D-41CF-8ADF-0D41620CB6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d882fd781b695936558294c9cd66d088a3593510","datavalue":{"value":{"entity-type":"item","numeric-id":1278524,"id":"Q1278524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b662c8bbb4ac14f24cd8fba8ddda2d7eeb24386","datavalue":{"value":{"amount":"+0.8963552","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":"Q1600003$FFA3BB6A-B5FA-4F78-955B-9586A2FE578F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f626a39893cb6f4cb57f117eacdae2641edc73a8","datavalue":{"value":{"entity-type":"item","numeric-id":475200,"id":"Q475200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a51b0bcdf02d0cd8a6bdbe6e33be7e90876688a","datavalue":{"value":{"amount":"+0.89520156","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":"Q1600003$5A87DB71-EFE4-4FCA-9E79-9196B8A5ECE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee89a80d8406595e9665e0ca671f27389ec43796","datavalue":{"value":{"entity-type":"item","numeric-id":2779799,"id":"Q2779799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f27b661f18b72bd0d5b0d59d3ed24a09bae8ac96","datavalue":{"value":{"amount":"+0.8947991","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":"Q1600003$7449D4E2-62FE-4F83-B82F-C10C674E5D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3937b0360f43cd456105d94541987fa335353471","datavalue":{"value":{"entity-type":"item","numeric-id":2142676,"id":"Q2142676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98dc3f0e1d79d1fd67d398777ab9ea5f79922550","datavalue":{"value":{"amount":"+0.8928739","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":"Q1600003$316673CA-C4A0-4342-87E2-1E426A924069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14262706d059417733faea406438d73f3d4e20f4","datavalue":{"value":{"entity-type":"item","numeric-id":969518,"id":"Q969518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfa86c246556f5fb1985fab52563b7d66be77f6e","datavalue":{"value":{"amount":"+0.88662726","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":"Q1600003$F51EB366-0300-48A2-A831-4DFA9EC27E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"675e1c92ad1959d60dcc1c2fa06c5f04b92870a2","datavalue":{"value":{"entity-type":"item","numeric-id":1662160,"id":"Q1662160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ad5843b10bf1aac78cca798e4115857b69b3ce5","datavalue":{"value":{"amount":"+0.88282716","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":"Q1600003$BC585C06-512C-489C-938D-A98FF504480E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdb53217836a42450dae0c2f937718e91b318d69","datavalue":{"value":{"entity-type":"item","numeric-id":1112719,"id":"Q1112719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8132c0a209fe930d23ce9875ffffdf6fdb56aa15","datavalue":{"value":{"amount":"+0.87942106","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":"Q1600003$0CFA2B7E-3D56-4663-BED5-E3B4BDF50B42","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of some special types of timetabling problems","badges":[]}}}}}