{"entities":{"Q1111388":{"pageid":1122137,"ns":120,"title":"Item:Q1111388","lastrevid":66688671,"modified":"2026-04-12T11:59:39Z","type":"item","id":"Q1111388","labels":{"en":{"language":"en","value":"On the domatic number of interval graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076645"}},"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":"Q1111388$DBFFB5A2-9040-4F42-B73C-490436A0E7DA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac9461acd62b2f67e09deddc8b0a957473918d79","datavalue":{"value":{"text":"On the domatic number of interval graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111388$33F4BE2D-2C58-4F51-868B-B30F006AF183","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"53884d470580c98780e144cd2e6e9779884675d8","datavalue":{"value":"0658.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$C3FFAAF7-3B38-4E84-8C66-08880DFEBECE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ad7c3f772bf34614a2920490282a308f541fdb8","datavalue":{"value":"10.1016/0020-0190(88)90173-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$74382171-E3EF-44EA-A90E-F043EB0A377C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f04044f52fa6e66fcf9bb794751a3ff14954e256","datavalue":{"value":{"entity-type":"item","numeric-id":218028,"id":"Q218028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$676B9F3C-D1C4-4E5C-BF9C-504AF3643D66","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":"Q1111388$6C358EAD-AA05-48C9-A298-FE580D4384FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111388$EAE2F3AE-6057-4194-AD64-D59EE60C039F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d5aca3ef8795b2ccddb764e77e3ac82e46167c18","datavalue":{"value":"A dominating set of a graph G is a subset S of the nodes such that every node of G is either in S or adjacent to some node in S. The domatic number of G is the size of a maximum cardinality partition of the nodes into dominating sets. We present an \\(O(n^{2.5})\\) time algorithm for finding the domatic number, as well as the desired partition, of an interval graph (which is a graph representing intersecting intervals on the real line). We also give an O(n log n) time algorithm for proper interval graphs (graphs for which no interval is properly contained within another).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111388$0234A424-C7B1-4E9F-975C-45DB15F1DA5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$1F8C29FF-08A9-4003-8358-EC8B74DA1813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$D501B777-9CFE-4170-8114-2C00E22FE4F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fddfeb54b8218f59d44d50e67a226946c67be4bf","datavalue":{"value":"4076645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$0796C90E-596F-4091-850C-9368F849AB4C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111388$8F6A10C4-675B-4EE5-953A-677DDE0C13CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"325d444ec4dfd06d216b15f4f1108205658b2ac9","datavalue":{"value":"domatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111388$96C34316-AEAD-432F-91A8-6835A6FF5620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d59ab2c83e0dbd443ebc1f3d0412b712509c0917","datavalue":{"value":"interval graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111388$F1E8F5BF-5D41-419E-8686-B3ADA41ACE2F","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":"Q1111388$DB219CD6-0FD2-41BE-B104-7BB181793584","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"987abdb7eabf5dc832c93ffe8d891e7328dd095b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90173-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111388$28C477AB-F6F5-492E-9E45-D77E525BF297","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a31eaec91618baf0b5c7239a4d80e4fcf1f8637","datavalue":{"value":"W1991307540","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111388$9E2A9CFE-1D7B-4A02-A5FF-948D3AE6D78E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb58559dbcbec2468b43206f2492cdb153b63a53","datavalue":{"value":{"entity-type":"item","numeric-id":1050117,"id":"Q1050117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$51C9038E-EEFC-4BF5-B960-77A5D745EE5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c6807bb69250e5f3aea352a72773fdcbd3a35f1","datavalue":{"value":{"entity-type":"item","numeric-id":5903263,"id":"Q5903263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$B7DB8804-3A0D-4304-B310-326D430E1B40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9348e1c9ad5465f71daa6350b7dddd13e3961e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1098312,"id":"Q1098312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$3799EB09-20EC-45F1-B737-A9CD72EBA66B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5f52e309359b78a163c61f97a76c6a6ce5a5096","datavalue":{"value":{"entity-type":"item","numeric-id":3792718,"id":"Q3792718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$87820EC6-DAAF-498F-9DF4-4E80298B41CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce3a94db921e6cba7ad432e9dc6feb40cc6db53","datavalue":{"value":{"entity-type":"item","numeric-id":1066921,"id":"Q1066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$C38332F3-9F52-4C0C-BD54-CC855068A6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d207798ab208e2d6135aa6be4f21281e7287368f","datavalue":{"value":{"entity-type":"item","numeric-id":3944643,"id":"Q3944643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$7E180265-7470-49C7-93F6-18E3F3FD2C72","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":"Q1111388$95FBA26A-4E45-4B16-8E15-E2A458B03837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd41c612f3888f5339ad5bcc277a720f58a90e7","datavalue":{"value":{"entity-type":"item","numeric-id":792885,"id":"Q792885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$58E5C529-334A-4C8F-9ECB-17632F5E2940","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":"Q1111388$63EEEE37-092E-4F5F-89BE-9A4E8FA4CB87","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":"Q1111388$6BC8512F-9F3C-4958-BDDE-D0E1009FF5F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d22d1a66627507c9e175f0940657f78d850ce78c","datavalue":{"value":{"entity-type":"item","numeric-id":3956413,"id":"Q3956413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$EA0F61FB-1B6D-4C6B-8FE7-D095FDF4DBE6","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":"Q1111388$2A6637D9-D4AC-4A54-B20F-54A757DC883F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc14983fdd6715fa4e9a1fc5c1e2adec0403bea0","datavalue":{"value":{"entity-type":"item","numeric-id":3898496,"id":"Q3898496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111388$CF1838CF-E0E8-475B-9A95-3A6C0F5F2D75","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bfc76d981bfc5a69c1e9f10fc3b1916eebfebcb","datavalue":{"value":{"entity-type":"item","numeric-id":5749323,"id":"Q5749323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68b03ea5ad49d7851fbeaeac9ca8fbac5e202739","datavalue":{"value":{"amount":"+0.9558910131454468","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":"Q1111388$D79A06AB-5654-4692-8E76-CCBE9EE413DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a41a36323f6eb118bd70403f1ffa12526a2a9632","datavalue":{"value":{"entity-type":"item","numeric-id":4881283,"id":"Q4881283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b4f4b2f832672d14d131da03447c192b857fabc","datavalue":{"value":{"amount":"+0.9122074246406556","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":"Q1111388$E698AEF7-D925-4356-AAAC-0C1D18F194A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92df10514685451ad58db670a979af83d2f078fe","datavalue":{"value":{"entity-type":"item","numeric-id":1262139,"id":"Q1262139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e471e2407caf56f549f40c0d2a00b25436141ae","datavalue":{"value":{"amount":"+0.8783512115478516","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":"Q1111388$D5E89554-0491-4AFA-88D5-77ED280A2C0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13744b7c84664d75273503de39dfe7db27131f14","datavalue":{"value":{"entity-type":"item","numeric-id":5903263,"id":"Q5903263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"193e75b3747eaa9ca4817894feab6d15b1d3dfe5","datavalue":{"value":{"amount":"+0.8547016382217407","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":"Q1111388$F837364A-A475-484C-954B-D455F989CE3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb6319b44e48cd1c7b0ef992fcd8dc44945df198","datavalue":{"value":{"entity-type":"item","numeric-id":1066921,"id":"Q1066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b410c4a17515ee30c0ce2be8f3a0a9848d826ee","datavalue":{"value":{"amount":"+0.8485586643218994","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":"Q1111388$4B11C326-3B4F-4775-BC28-EC8749D22C26","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the domatic number of interval graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_domatic_number_of_interval_graphs"}}}}}