{"entities":{"Q486988":{"pageid":488755,"ns":120,"title":"Item:Q486988","lastrevid":62261256,"modified":"2026-04-11T04:52:48Z","type":"item","id":"Q486988","labels":{"en":{"language":"en","value":"Solving the 2-disjoint connected subgraphs problem faster than \\(2^n\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6387687"}},"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":"Q486988$F25C0634-FCDE-4DF4-A0A5-BE069B510B24","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b206749705995054c2677b9a675f06b63816083a","datavalue":{"value":{"text":"Solving the 2-disjoint connected subgraphs problem faster than \\(2^n\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q486988$71716E20-84DC-41DC-859A-DDEA75CA2E02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0afae361c9f0df3b5d109fa5b23ccfac5fb54b2","datavalue":{"value":"1306.05125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$8CD7B165-8B02-4A38-803B-60BB02BB0E89","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"126ad086c11d29b44b6dea551efd67f8beb1ce87","datavalue":{"value":{"entity-type":"item","numeric-id":255282,"id":"Q255282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$494DFF98-C5EF-4F1B-A309-E09D9F0E0E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8393ad112fe8548ea40a3793cd450c8b7586360e","datavalue":{"value":{"entity-type":"item","numeric-id":255284,"id":"Q255284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$647C364D-9B24-4DF3-9EB1-A2E87B5B3E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e229a7272481236f52fa95a4480b3f630728e07a","datavalue":{"value":{"entity-type":"item","numeric-id":262250,"id":"Q262250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$CAA63207-2127-4A43-9B01-1269606596BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"caab9bc3c449d51ee97f8a392883cc297dede7db","datavalue":{"value":{"entity-type":"item","numeric-id":486987,"id":"Q486987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$CAEE175A-F74C-4A3F-ACB4-4FAF60AE489E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$F228FBF8-A368-4380-B8D1-64F93319D905","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"23e6ba576eeca2c6f926b5ca32f399afa8cf58c8","datavalue":{"value":{"time":"+2015-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q486988$200C9506-957E-4887-A0E3-3097FAB0DC2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$61EF8AA0-D382-4696-AA2E-82C43CC40C4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$4F9348D3-9BDE-4C5E-8163-E595BAF80575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$983617F2-A0A6-4FDE-BB63-DA151E5B96D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$6594C6BE-8D95-40E5-B2FE-42BAFD397644","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02a6e2a177d163dd6b5c1bee73f07652ef2484b3","datavalue":{"value":"6387687","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$7E100FAC-3BA9-4CBA-ACC3-4476748C68F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3f05553a5308936a7205a0d3afccb9b8d271916","datavalue":{"value":"exact algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q486988$D46A6108-6B1E-48A0-AA9D-97E288A84CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"230345b97615ae50e225fdd221fde30bb66df7d7","datavalue":{"value":"\\(2^n\\) barrier","type":"string"},"datatype":"string"},"type":"statement","id":"Q486988$6A24D8E3-4E68-452E-8A58-B35B2714F444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1aad0e9f2720cca131a115353e665fe83a3a6a2","datavalue":{"value":"2-disjoint connected subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q486988$26A67AA3-771F-4A5A-8892-500037D0C5A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040e5cadc2542137fa22dc2efc65268bb08b809c","datavalue":{"value":"kernelization","type":"string"},"datatype":"string"},"type":"statement","id":"Q486988$6F6EE815-4E61-42E4-89FB-A70525BE0E5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b0974d841ba27603503b56afd092463f7ab4b17","datavalue":{"value":"exponential time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q486988$27EABA50-1296-4F0A-A523-CC655B7134CD","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":"Q486988$3073A0E2-083D-4EB5-B673-9EC90FFD3269","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1d4bfbb5a299bc80449cda92663330fc9acf77e","datavalue":{"value":"https://doi.org/10.1007/s00453-013-9796-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q486988$53F6353D-52BE-4930-ABFF-0CEF46862220","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b895dc7af8a11838058c3bfaf57a5681b2deaa6d","datavalue":{"value":"W2126913088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$5B9DF3F4-7564-4C8C-84BF-F1030A2734A2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b3092d0d23416a6df074c83d3a66e7241d827bd1","datavalue":{"value":"Q59399105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$EF0752C9-19A4-40E9-B47D-5648FEE85FB1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f6f0e024114319e5eb6aae9883a0233df2f35ab","datavalue":{"value":{"entity-type":"item","numeric-id":3549598,"id":"Q3549598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$B7821CD5-8764-4F1E-8C34-39756DC99E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d078e21f9718b01f228742d1c2f5371b675a0f5","datavalue":{"value":{"entity-type":"item","numeric-id":3558013,"id":"Q3558013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$03B1BD9F-0D1E-4841-8A92-896343487BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a4c23b508911cd4dee06950b209c7fd3b1801e","datavalue":{"value":{"entity-type":"item","numeric-id":3656852,"id":"Q3656852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$61D4AD79-1080-49F4-9609-D165562DDB84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b94320d282f337134f4ff1c8982024ee8cf3a9f5","datavalue":{"value":{"entity-type":"item","numeric-id":708223,"id":"Q708223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$30F1D957-8BBB-4499-8698-1EFEB4E70AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee2b05e223accd03a5107ea15814aec8045a1ed","datavalue":{"value":{"entity-type":"item","numeric-id":5494962,"id":"Q5494962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$9D1E28B9-D51D-483E-AC5A-99C49081377B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a5a90f4e89d8ebfebb38032743a027b2669c16c","datavalue":{"value":{"entity-type":"item","numeric-id":3092238,"id":"Q3092238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$C8893140-07E2-4999-8899-1DB291CBB252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3ccd52480738f16f133e453f288930971d4db9d","datavalue":{"value":{"entity-type":"item","numeric-id":4962605,"id":"Q4962605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$CA282F3C-305A-4220-B0CF-69F9D1DF8011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5c75c62c5428390cc950e20399ad1a0c1b72a25","datavalue":{"value":{"entity-type":"item","numeric-id":3638049,"id":"Q3638049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$D6B5BA39-BF48-497A-B2C5-589E5D10F659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08679e1302d53c12ee04f803b2320a1e4c7b1a0b","datavalue":{"value":{"entity-type":"item","numeric-id":606873,"id":"Q606873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$A8B56011-0A7D-4EB9-A8F6-ECE98A53EE2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f77347970e953e82d8dddf1fddbdb2c14d24ef6","datavalue":{"value":{"entity-type":"item","numeric-id":3452221,"id":"Q3452221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$033A1CCB-3691-4718-9C8A-CFF9FD4CB5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1aaeceb2ba9303b14fe53a9dd8332481c6b276","datavalue":{"value":{"entity-type":"item","numeric-id":3092237,"id":"Q3092237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$203F104C-8A50-4F9C-BB63-22EFE01A27E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2613f25823307234975c74e5ad71025bf1edca1e","datavalue":{"value":{"entity-type":"item","numeric-id":419504,"id":"Q419504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$8D4B6C22-A114-4084-99B7-AF0B6BE05C6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$C5DC251B-FFF9-48FF-B424-5F5FEA9FB768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5762d647bad67eb99de6bbf40a6d31cb9ada3a18","datavalue":{"value":{"entity-type":"item","numeric-id":5365080,"id":"Q5365080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$77E34408-9400-475E-9F29-88847F6EB242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4226e3e65547158ea8072512457653ecc8bcdac6","datavalue":{"value":{"entity-type":"item","numeric-id":5417690,"id":"Q5417690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$994DD8CF-9FAE-4CC8-8D6E-0CA032A6C90B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b215c6c3f517a8eaa0b6b2501305505d97397a9a","datavalue":{"value":{"entity-type":"item","numeric-id":650911,"id":"Q650911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$FA26682C-2FCD-457A-BBE9-F8110A17D703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$B4489557-68A7-41AE-8A5F-77F245C9FD05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0489d5b5d598bfa6547ce694013b3158b5df85a","datavalue":{"value":{"entity-type":"item","numeric-id":2864321,"id":"Q2864321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$137161C8-D50A-4991-8431-89F767E8C770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2b766955624b72c0113a5aa03b5180194e3a575","datavalue":{"value":{"entity-type":"item","numeric-id":3639274,"id":"Q3639274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$55554CEC-7E45-4C76-92BD-07A408983AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ede4cf54040a9ef2e1d48b015287cfb5cfffc5","datavalue":{"value":{"entity-type":"item","numeric-id":1034603,"id":"Q1034603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$478BE6E2-6E2D-406E-A91E-2713584ADD55","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe745387bfcc6b967c08a522abc34230846fb8f3","datavalue":{"value":"10.1007/S00453-013-9796-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q486988$8272504E-BAF6-401A-92EB-2DEA24EEE70C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51543bfebd874af64271ba5116446cdf66c83cd1","datavalue":{"value":{"entity-type":"item","numeric-id":2894465,"id":"Q2894465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6352151fd845921e168deeb1bc6b92351b671be","datavalue":{"value":{"amount":"+0.9957135915756226","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":"Q486988$84CEA89F-BA4F-48B7-B861-2C0AF16D76AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2acc1c278a86e35a66aabe69c75ce529ce151732","datavalue":{"value":{"entity-type":"item","numeric-id":2864321,"id":"Q2864321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b052f2ac51c8eeef8efc6c2515b0948591c6357","datavalue":{"value":{"amount":"+0.8471503853797913","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":"Q486988$DA81D2DE-438A-43DE-B96F-5A68485867A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38a29e91237094ebacc8867d1cf0ddfd1b30ff9e","datavalue":{"value":{"entity-type":"item","numeric-id":3652306,"id":"Q3652306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba987cc44cf7f0e3793fb6e2152c1f9a983a4616","datavalue":{"value":{"amount":"+0.8216009140014648","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":"Q486988$72FC3867-78E6-4E5C-8F6B-AE86FBEBAF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a4e215b549c04169a04513b67048398d3013dd6","datavalue":{"value":{"entity-type":"item","numeric-id":650911,"id":"Q650911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28c6a2a9235bac2975d573b48a4fa21ad62f224a","datavalue":{"value":{"amount":"+0.8169453740119934","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":"Q486988$F28D2051-F6F0-40F0-8E8B-C7752A349752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"908230b8d81722e44d4f3a57e9e69aaaee1e63c5","datavalue":{"value":{"entity-type":"item","numeric-id":1034603,"id":"Q1034603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"958d297cae605527e008327c3620b98a87370ee4","datavalue":{"value":{"amount":"+0.8014963865280151","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":"Q486988$3CDFB85D-F6C4-4599-B61E-E8CE37E97E82","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q486988$938882D0-22E0-44A7-9894-467F939DD4EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving the 2-disjoint connected subgraphs problem faster than \\(2^n\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_the_2-disjoint_connected_subgraphs_problem_faster_than_%5C(2%5En%5C)"}}}}}