{"entities":{"Q1108809":{"pageid":1119558,"ns":120,"title":"Item:Q1108809","lastrevid":66735045,"modified":"2026-04-12T12:31:00Z","type":"item","id":"Q1108809","labels":{"en":{"language":"en","value":"On generating all maximal independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068316"}},"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":"Q1108809$46BCEBFD-524B-4E0A-B05E-8AF0C0FEAE8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d69eb09a0feb890e2ccb362add11b5c720632cc0","datavalue":{"value":{"text":"On generating all maximal independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108809$41CC35D9-6B86-4A87-A317-151980CF9365","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c99291d12e0cc55da73c37479e72963d9a67cd94","datavalue":{"value":"0654.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$502C924E-2091-414E-AF0A-02EB9A26280A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"015b310a0979ccf8627a8799162f04ffd8b715a7","datavalue":{"value":"10.1016/0020-0190(88)90065-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$32F31F1C-3DBA-4B4F-A572-1086E454F04C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ecf2d8824396c280beb38bdd66733991f0508cba","datavalue":{"value":{"entity-type":"item","numeric-id":721935,"id":"Q721935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$611D12B5-4E89-4FC4-85AF-EAEA1FA90DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$0EE007BB-630E-4371-8BA8-D7B8E02A6582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4703623e4fcbefcd3931d7b75f8faed8c58b1ed6","datavalue":{"value":{"entity-type":"item","numeric-id":222484,"id":"Q222484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$CCD944B1-5675-4348-A76E-947465F20EB5","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":"Q1108809$92DE0E63-28E2-4167-9290-D3C5B9DAE1E5","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":"Q1108809$71D84F74-761A-49D5-A2BF-B6C2EA1B1D07","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b7ad6c788934abc73d249be1c5676a9581bd818","datavalue":{"value":"We present an algorithm that generates all maximal independent sets of a graph in lexicographic order, with only polynomial delay between the output of two successive independent sets. We also show that there is no polynomial-delay algorithm for generating all maximal independent sets in reverse lexicographic order, unless \\(P=NP\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108809$F704D435-DBD6-415A-9E5A-FBF152951786","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$16551FEA-57A8-4DB1-9DC8-FFADC8798A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$79AB0912-794D-472E-A3CF-47C05BCCD60E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"41132c9a923b3fe4bc6a8449fe8f5c150513b442","datavalue":{"value":"4068316","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$F9D15DD3-7A97-484C-9F5B-D714BDD4779B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108809$B17EAEC9-F86E-4F5A-B1A1-1874AC30E72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108809$9EF193C3-D0E0-4F69-8D9B-5140FBF23C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108809$68FFD451-9C86-4F6F-9093-A10290A3C26C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22683c06fedcaa7012c349358a0eb5ee9c463256","datavalue":{"value":"lexicographic order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108809$FFEE74FC-5D41-484A-8216-860F382B5B83","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":"Q1108809$DE8C0B70-2E02-4326-B17C-26DC5E2B23B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c66c6a45ecdc0f3d03976c32589309ce8048bd9e","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90065-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108809$305DCCBC-D2F7-4B1A-89B2-34BD43DE5509","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"da1eff0fe4e31dd4462af7ae29ca449cf5a56e31","datavalue":{"value":"W2007940874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$868F5708-5298-48D0-B2E3-A63380CC4A5D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"923e3da516ffe87deabdb04623cf21b3ec5e69f7","datavalue":{"value":"Q56210424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108809$8FE2FC80-557B-4B85-8207-C6B9A0B941A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$2238BE16-FF11-4B92-AB75-73908E8663B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c48713acd3037a2e87e8e9b9cf4a2e7ca04ddfe","datavalue":{"value":{"entity-type":"item","numeric-id":3771671,"id":"Q3771671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$63709A70-4A75-4786-B13D-4FFA38ACA468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cee622c8004588ce4ee327462c9cddb2144c21dd","datavalue":{"value":{"entity-type":"item","numeric-id":3890128,"id":"Q3890128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$CF7A1259-DC8C-4C5E-A1A9-800E7C29B11B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b40d6bc065ab5a3b1d916a6dbfb213e2ada9369","datavalue":{"value":{"entity-type":"item","numeric-id":4173359,"id":"Q4173359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$43CF5324-9B0F-4D8E-9DFF-9A880A4D2A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"040b7b9fbede4032e8348103c4d815e16fc87c56","datavalue":{"value":{"entity-type":"item","numeric-id":4075503,"id":"Q4075503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$D3D791FA-74FF-42D7-8145-6216BD7A30CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb85e2a08b123210f7ea1cf8a8c1c958121dd184","datavalue":{"value":{"entity-type":"item","numeric-id":4138754,"id":"Q4138754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108809$3C8B9AF7-176E-40CE-A227-88021D3B4BE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"761e4c01a37a5a070512847bf48b179e8dfb8529","datavalue":{"value":{"entity-type":"item","numeric-id":5931790,"id":"Q5931790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07a44e91524ec0b445e2b0715cfdd77c229ab2a7","datavalue":{"value":{"amount":"+0.9340682","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":"Q1108809$CFB580B1-F667-44C5-BC69-721FBE83C3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f275910462f9602b1298ad1fa23aa9864491da3e","datavalue":{"value":{"entity-type":"item","numeric-id":1756132,"id":"Q1756132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ef907dd3b44b9913c01b95ede6a00251b5a6e57","datavalue":{"value":{"amount":"+0.92265403","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":"Q1108809$B096ED50-09E1-4DF4-8E46-67BC9C4CE198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0843fb88b6b95256c896af21fe3948b13a121789","datavalue":{"value":{"entity-type":"item","numeric-id":3641025,"id":"Q3641025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b3a211d84820eaacf7a7610cdc13f71d33a90c3","datavalue":{"value":{"amount":"+0.9163451","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":"Q1108809$4A887B74-0C98-40B1-87FA-65B77B79F0F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"884996bb3c710830ce84622aab27e31355b808c0","datavalue":{"value":{"entity-type":"item","numeric-id":4304413,"id":"Q4304413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"430e7316e0cdbf26d4fd7047983606745e769ea4","datavalue":{"value":{"amount":"+0.90552574","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":"Q1108809$4AF1EEF8-73C9-4CF1-97B3-1373ED1AD7F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b94a430007653b6fa5087dfb0f669e77629e3d9","datavalue":{"value":{"entity-type":"item","numeric-id":1328528,"id":"Q1328528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"381739a2cf70a7dc9c544d848914159a1ecf0649","datavalue":{"value":{"amount":"+0.9028497","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":"Q1108809$43914C30-CB60-4178-84BF-EDB079C51D98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e67af38bed3c2080cbb90104289abdc78eb65eb5","datavalue":{"value":{"entity-type":"item","numeric-id":5364240,"id":"Q5364240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0b3339da6c8763b6685cc94a055e1d3b77a30bc","datavalue":{"value":{"amount":"+0.89683545","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":"Q1108809$EA88A025-A127-4CA2-BE06-C7498B83A8B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"099029809b03ae74a528a8efb40c6471fde2f8fe","datavalue":{"value":{"entity-type":"item","numeric-id":4486258,"id":"Q4486258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11148f1b4f24a0da488ff1f202ddae271090a9ea","datavalue":{"value":{"amount":"+0.89361566","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":"Q1108809$3358A23C-E113-43B9-AED3-556B3433E53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d850cc6932cffc9f7dd934b1a4d41852daf4109","datavalue":{"value":{"entity-type":"item","numeric-id":2181736,"id":"Q2181736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eae28829abe5c506cd965ca2557631843206b85d","datavalue":{"value":{"amount":"+0.8900584","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":"Q1108809$3478AB86-7D41-434E-BE74-8668621F8B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421e63aaaedf2f1e9fa78d8af4e786f282484ffe","datavalue":{"value":{"entity-type":"item","numeric-id":2026337,"id":"Q2026337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86de634f222db00a84daf90af6e49f54039ed807","datavalue":{"value":{"amount":"+0.8882263","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":"Q1108809$CDAA10DC-0882-4A73-93D4-B0E6EFF71A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bbd0acec2b30cdc1fd627f22454e03f8f1cdd2e","datavalue":{"value":{"entity-type":"item","numeric-id":4864968,"id":"Q4864968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bfcaa6f74e40e5dfe5dbcefa5f04cb1abbb0c57","datavalue":{"value":{"amount":"+0.8851525","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":"Q1108809$C910C31F-B5D1-4A4F-8306-ABD849F2CCDE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On generating all maximal independent sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_generating_all_maximal_independent_sets"}}}}}