{"entities":{"Q1408809":{"pageid":1419549,"ns":120,"title":"Item:Q1408809","lastrevid":70353549,"modified":"2026-04-13T14:11:58Z","type":"item","id":"Q1408809","labels":{"en":{"language":"en","value":"Finding a \\(\\Delta\\)-regular supergraph of minimum order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1985914"}},"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":"Q1408809$B8F6A59F-2946-4D3D-9C8C-40D0E65F49ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe67f7dd06d125f736528526d51452c956fc39a5","datavalue":{"value":{"text":"Finding a \\(\\Delta\\)-regular supergraph of minimum order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1408809$9ABDD383-5F8D-4E9C-B7EC-99E516CDB073","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ee6cb10777729a6c7b91df75192382bab3b3db3b","datavalue":{"value":"1032.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$572F4586-30CD-4590-B1C4-B324951580B8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9cfff13b3f86e6bfd2d439cebfe1646dca0cbf1c","datavalue":{"value":"10.1016/S0166-218X(02)00413-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$2E71B73A-8984-42C4-9AC4-1EB5FC6958DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"941ae452fdd381d259af5a517a03b54a56e10b77","datavalue":{"value":{"entity-type":"item","numeric-id":418789,"id":"Q418789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$05D11762-6449-4609-93A0-2125A62291D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"926e613762971a9014a8b1ed071772bdcf0a0812","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$8B0D6310-EEEB-4246-ADCF-6EBB1412B7D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"665cea1ac049fad02d3990496a44dd0a8e274e27","datavalue":{"value":{"entity-type":"item","numeric-id":226814,"id":"Q226814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$948D4665-3B34-4531-AAB7-4C9C7F4C26D0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$6DF6CF4D-B931-42D0-B194-4913E45BD6AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f37244814e4fbe2fab0838dfe21d7174c9a47265","datavalue":{"value":{"time":"+2003-09-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1408809$16CBD02C-3D51-4660-B4B5-D81B2550BD10","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09f3ff19afbf44cb7e4ec88ad23cf6e0d6c38975","datavalue":{"value":"Since various algorithmic graph problems can be reduced to the case of regular graphs, there is a motivation for constructing a regular supergraph for a given non-regular graph efficiently. In this note the authors show that, given a graph of maximum degree \\(\\Delta\\), a \\(\\Delta\\)-supergraph of it of minimum order can be computed in \\(O(\\min\\{\\Delta^{1,5}|V|^{2,5}, \\Delta^6+ \\Delta|V|\\})\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408809$36D1FC59-BD83-4A16-9990-90C17AE6108D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"86318d3c96cef410d7aac68684401e5a8e817946","datavalue":{"value":{"entity-type":"item","numeric-id":708333,"id":"Q708333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$B2C359F5-AF6F-4B7B-A0E9-B7849282426C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$43255A4E-1DEB-4D19-A00B-5026F3638F7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$A52F014D-3BF2-41A9-9E35-9822AE752D1E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8959a4797254df2ad8c92e84aa5cdc9e7ffb8b91","datavalue":{"value":"1985914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$874A4226-F1D5-4971-8E14-A9E0EDD4EF0B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d62de962fdd8fd621a15709112df0b0286af83c","datavalue":{"value":"regular supergraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408809$677A7947-D651-49F4-AF30-E93E3958AFD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54448692e2cd98ec1c97e09a959dffe14fbbf8d8","datavalue":{"value":"regularizable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408809$8917294E-586F-4254-A626-54C0CEA65DBD","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":"Q1408809$5A0A27CA-FFE3-4081-916A-8FF6A0FDC17C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c4c5fd5b2b1788a608aa1b9b8c3af194af15f158","datavalue":{"value":"Q59567881","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$03FAAD02-9D8B-4E6C-8345-79F36A6D3CD2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d41dfc654366d94fb12d2debb5573c3c7b3dcb18","datavalue":{"value":{"entity-type":"item","numeric-id":1155628,"id":"Q1155628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$FD59CF0F-E73A-43E8-A8F4-5686DE223DB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"158074026b12bcc0c8d303c2782c8ab65c0b799b","datavalue":{"value":{"entity-type":"item","numeric-id":5187322,"id":"Q5187322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$AC440AE6-720D-4F98-A608-26EE5E1CFD86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e35ae43123b97f75931c21aa049faf5ddd6c7e","datavalue":{"value":{"entity-type":"item","numeric-id":4845365,"id":"Q4845365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408809$2BC53F15-AF85-4A7C-9CBE-AA2E677F0B99","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e90f0c97660801ab54e5d16fd109ce2e7ddc698c","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(02)00413-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1408809$20AB05D8-243E-4700-B78B-4F4DD25BEBA7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"45bb1afb9cf0a751ceeb07b0a91f2f13bb718da0","datavalue":{"value":"W2066999332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$48B3023B-5B5E-4E60-804D-080756338B11","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"95d2ea679af66aa929728f05bffe30f1117e7286","datavalue":{"value":"journals/dam/BodlaenderTL03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408809$AFBC6D04-F07E-4CCD-892B-3AED725BD8F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76ffa7b84323ba162b23c46dd71d76027b201e7d","datavalue":{"value":{"entity-type":"item","numeric-id":2657064,"id":"Q2657064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f207aefb4eab9331e54de5aea0d9129a5d695903","datavalue":{"value":{"amount":"+0.8563969","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":"Q1408809$651C9CED-68AA-4471-BE9B-9C708A34F918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fd8a6eaca743ba4b8b4391922c48ccb0df100c5","datavalue":{"value":{"entity-type":"item","numeric-id":659824,"id":"Q659824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c7a2393c05ae0673c61a349bd513e3ccd457a97","datavalue":{"value":{"amount":"+0.8540479","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":"Q1408809$A3D26259-C068-4B18-A609-D7455F748349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"208e53b3157002daf5d926eb244d08f9ec9cd47e","datavalue":{"value":{"entity-type":"item","numeric-id":1613362,"id":"Q1613362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f0aca9090ebd7cfb73f170f6796e2cca9c00094","datavalue":{"value":{"amount":"+0.85198766","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":"Q1408809$5C975DB7-B172-46BC-B4F0-878DD684CE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efc621665b119f185a808ab85e90661ba20d4cc8","datavalue":{"value":{"entity-type":"item","numeric-id":1583672,"id":"Q1583672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d9504bc3ec90e63c9f3c361e257afd2c9e7f6d1","datavalue":{"value":{"amount":"+0.85031384","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":"Q1408809$CFABD796-57FF-42FF-BEAA-5030B456317F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b40fa6a1ac0c3d31e52413bf829256bba3a4cbd2","datavalue":{"value":{"entity-type":"item","numeric-id":3701449,"id":"Q3701449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01b9f67cfc4f8cb78b4d1291a750fc6c207e8931","datavalue":{"value":{"amount":"+0.84699625","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":"Q1408809$E175944F-955C-4752-A7A6-123A96E545D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0d314f7cde1e9beb24a54c5b35f95cbfc65b570","datavalue":{"value":{"entity-type":"item","numeric-id":4715282,"id":"Q4715282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5d3f491d6d661096427eb582783d0985f1b4285","datavalue":{"value":{"amount":"+0.84504235","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":"Q1408809$85A82396-8CAB-426E-9C5F-2172330E7866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99b056710b43ecf0a082b2015abc13ef1cf8bb5a","datavalue":{"value":{"entity-type":"item","numeric-id":3824340,"id":"Q3824340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ec42814f684477cf517cbd2ef0abf78e88c74c","datavalue":{"value":{"amount":"+0.84441715","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":"Q1408809$F8A62C83-91C6-4754-89C3-7F4DF7116371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b01eb67c8263224951dcc0423abf70db410da411","datavalue":{"value":{"entity-type":"item","numeric-id":4957519,"id":"Q4957519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d58ad539e7f538fded7012ada3a212a0bb577b4","datavalue":{"value":{"amount":"+0.8355314","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":"Q1408809$B7A137F5-B039-4392-A62E-8CCEC5D99EBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ec14ebb9bea2e5e006d5a08487e5f0ed25aac45","datavalue":{"value":{"entity-type":"item","numeric-id":3442866,"id":"Q3442866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"418854bf232480a186f15b73be3896736b6f2cdf","datavalue":{"value":{"amount":"+0.8335039","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":"Q1408809$D088A336-7A7E-444C-BED5-3D38F96CEC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db553eee339260f36c4daa4c908ea2cd9493f1c4","datavalue":{"value":{"entity-type":"item","numeric-id":3501517,"id":"Q3501517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1b7c6af45cd5f59f7471adc40c1bbe271cb1fe1","datavalue":{"value":{"amount":"+0.8333093","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":"Q1408809$7B7574B7-172C-45DA-BE10-4C06518C9B60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding a \\(\\Delta\\)-regular supergraph of minimum order","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_a_%5C(%5CDelta%5C)-regular_supergraph_of_minimum_order"}}}}}