{"entities":{"Q1680494":{"pageid":1691235,"ns":120,"title":"Item:Q1680494","lastrevid":68125116,"modified":"2026-04-12T21:36:09Z","type":"item","id":"Q1680494","labels":{"en":{"language":"en","value":"A refined algorithm for maximum independent set in degree-4 graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6807517"}},"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":"Q1680494$0B73613D-B5F4-472D-9EF4-290747761889","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e9b199ba22a3d9291e4db67443bc5d10b0c91e6","datavalue":{"value":{"text":"A refined algorithm for maximum independent set in degree-4 graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1680494$390CE9A1-1EC5-4642-B2AD-18566FD1BC34","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1bc7778d2b28d479b711baf9804c2663544b1f2d","datavalue":{"value":"1408.90267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1680494$F5BCBD64-AD1C-42F8-93D2-04C59ACAA162","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8bb48d97aa42377c51cb11f373ef4c652a1af855","datavalue":{"value":{"entity-type":"item","numeric-id":255261,"id":"Q255261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$BC2A3059-EC01-4EB9-82CB-F5CE310F3277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ff31eda0378452e39418a5f890633895fac328b","datavalue":{"value":{"entity-type":"item","numeric-id":1680493,"id":"Q1680493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$9C8BCD0E-FE9F-4C27-A497-A076C465613C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dcf8815e3b257674fa147da7a4e7c92c91c0b3e3","datavalue":{"value":{"entity-type":"item","numeric-id":185429,"id":"Q185429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$F3C6AC07-3585-475C-A3CA-30E7076F3B19","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31b4e05ce401552e06c39f98d03ca03d178174b0","datavalue":{"value":{"time":"+2017-11-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1680494$8519DC6E-A1D3-4999-A0E0-E4650633539C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1680494$A4A45CCC-68D2-4B3C-B5D2-1F9A3C9F6023","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8bb38ccfdd88dc5a1a39f18bc6d1f4eddb1fed8d","datavalue":{"value":"6807517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1680494$DE1A1B33-EEB1-447A-B58C-A9D9FBA1DC3B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3f05553a5308936a7205a0d3afccb9b8d271916","datavalue":{"value":"exact algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1680494$6CD375AF-E841-404E-8F0E-0358A7AE5DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1680494$7F6735CC-3C3B-426D-B5E2-16C991601C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232465a4b21b2442783eb000a1c43840a0e6c26c","datavalue":{"value":"maximum independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1680494$E54C5C08-201C-4EEE-8F88-B6D2F3853E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6e7912c08173e2382e2d36fc1989bc3e0dfa0b","datavalue":{"value":"measure-and-conquer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1680494$FC3163BA-2F54-4302-B695-7A3BBA895287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ec37da8502f5286d6e407b7d5b29adece889aef","datavalue":{"value":"amortized analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1680494$D75237E9-C3AC-454C-8EFD-27B42F49FA5C","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":"Q1680494$3C8BE8A3-5874-4827-AAC2-C5F07FECA468","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"45ff222595ab0bc0ff6da28b8c825f4f41de1150","datavalue":{"value":"https://doi.org/10.1007/s10878-017-0115-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1680494$BCB137A3-5E4A-47E1-A6DB-F7175FA59361","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"946229e67134c967b15bf453e734300fbb127f8a","datavalue":{"value":"W2185104320","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1680494$8DF4534C-73A2-43AF-A9FC-C074685137D2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a3b5020580c5037e374b1980f126c042358e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":897878,"id":"Q897878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$902D2F58-529F-4E9E-B9FD-4B8B6B983482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0bfbd7fa3a42b021cc45e72745c47c3fc9d2c73","datavalue":{"value":{"entity-type":"item","numeric-id":3569091,"id":"Q3569091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$F156B5BB-3378-4397-8929-1D47568ADE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2aaeb5da73735f2a095fb653d55f184d0097047","datavalue":{"value":{"entity-type":"item","numeric-id":2428670,"id":"Q2428670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$9E0A9254-EEDD-4B02-ADB7-6E90484DA012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"841afe5368ee90e97418d34d48b610064f41e432","datavalue":{"value":{"entity-type":"item","numeric-id":708228,"id":"Q708228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$1CE180AE-507C-4DD8-B83A-A4C13A983606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e02730beba3cb19877504de614cde2f9e297a89","datavalue":{"value":{"entity-type":"item","numeric-id":5710807,"id":"Q5710807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$98E2B12F-4B9E-41D9-8299-0130FCB98058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f79f25b2035120832c510521c1dbe664461a9c8c","datavalue":{"value":{"entity-type":"item","numeric-id":2944526,"id":"Q2944526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$402C94E0-266C-4418-B18D-A389FF0304E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5898a3a95e1b0606e52aa24c79d5a6dc96dd2a74","datavalue":{"value":{"entity-type":"item","numeric-id":1045933,"id":"Q1045933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$6A899188-59BA-455D-A551-59F5B61AC7FE","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":"Q1680494$005E7108-32D3-4033-B163-5B17ED73F483","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":"Q1680494$42432B29-076F-4A11-B327-E0019F32A639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50d3d542ef1de9d7a1991d5df5ac9f34b9973659","datavalue":{"value":{"entity-type":"item","numeric-id":3525784,"id":"Q3525784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$1E353EBE-665F-4409-9340-D4C8343CD837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e63b41a9cc4f10c8e4a339e641363e7b7d7a70a4","datavalue":{"value":{"entity-type":"item","numeric-id":1935804,"id":"Q1935804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$807B30D4-6F0F-404E-9F99-8B57A3A44363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f62d6af5500a4d412b97619fad619bfd81886d8","datavalue":{"value":{"entity-type":"item","numeric-id":3745299,"id":"Q3745299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$7857AEB0-8F63-4627-B141-559BB64E6053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b0121c7ba60ffcae313c68826b18b0a1f5d8c1d","datavalue":{"value":{"entity-type":"item","numeric-id":2920136,"id":"Q2920136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$56224A2A-551C-46FB-8E42-8380A8C30754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5bb1b29744956ba0103c28c302bb59ee0fb90d5","datavalue":{"value":{"entity-type":"item","numeric-id":1026228,"id":"Q1026228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$F16C3315-D949-44F8-85C2-BE40F8B387D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb905b79b8a8b710686969dae7565d6e29bf903f","datavalue":{"value":{"entity-type":"item","numeric-id":3777476,"id":"Q3777476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$CC66D3FD-14BA-4212-B3A5-AE677EE0FFF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dc8a1faedec1647ff5e9aefae185cf306f2bc5","datavalue":{"value":{"entity-type":"item","numeric-id":4133117,"id":"Q4133117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$EE89D41B-66F7-4B8A-AD09-910E70EA805F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$35963156-B117-4197-AEE6-87131A44CBBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d168d73964c40fe6f486e2ac804dfab1ad005602","datavalue":{"value":{"entity-type":"item","numeric-id":3404455,"id":"Q3404455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$5A72B3A0-E25C-45BC-9633-36889ACDD1A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6ae6303e8be1c6b81b1204c9933a184d0b3b6d","datavalue":{"value":{"entity-type":"item","numeric-id":5199148,"id":"Q5199148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$FC2FE7C1-C0E6-48FF-B392-1922E8BD1E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a1c50286d28bc76f88b740e813467a4bdeb37a1","datavalue":{"value":{"entity-type":"item","numeric-id":2872097,"id":"Q2872097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$AE2115D7-B740-4072-BD4C-9BD7C8C5140B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e39b87f655b2c79ae14d56437833ff1b52721345","datavalue":{"value":{"entity-type":"item","numeric-id":896662,"id":"Q896662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1680494$864114AA-FDFB-465E-B1FB-375A27633BDD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb49b576fdaace0c3148fd44b4938c18902686c9","datavalue":{"value":"10.1007/S10878-017-0115-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1680494$98EF19ED-0A6E-4FD2-9739-1BB843AF727D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e937b6c280e6d3f0429f1219d93c111dafdaa4bc","datavalue":{"value":{"entity-type":"item","numeric-id":5199148,"id":"Q5199148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5556cee2999bf4728ad2437a4ce686a07d4ab8a9","datavalue":{"value":{"amount":"+0.935339093208313","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":"Q1680494$68FA1667-9798-43CE-BA02-6C005D760876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ac116279d53688ca52b0fc461b88ef0122cf9c8","datavalue":{"value":{"entity-type":"item","numeric-id":5405918,"id":"Q5405918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f2056ec89ba262f16199b94103c9296b7d8bd4a","datavalue":{"value":{"amount":"+0.8565035462379456","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":"Q1680494$8AF2B6A3-63C3-4D5E-A4E6-78D6568703AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00237c3b5fbaf6f4d382c64ca87dd21aba14c20a","datavalue":{"value":{"entity-type":"item","numeric-id":896662,"id":"Q896662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2aec22b51ae1364aecb58c098cadda40b4aa322","datavalue":{"value":{"amount":"+0.8513756394386292","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":"Q1680494$E1F78D4A-09C3-4E96-A3B5-532DA9844923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"342482c798308dcc94167036759d54eeea6a08e0","datavalue":{"value":{"entity-type":"item","numeric-id":3404455,"id":"Q3404455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0101ab691759e9974193ff37e48d6c0518e1cb1","datavalue":{"value":{"amount":"+0.8450128436088562","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":"Q1680494$69EA0025-6487-46A7-9524-EA30B0E9E90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d2d35fdc87d8f72526d95b25b390a7486532cc4","datavalue":{"value":{"entity-type":"item","numeric-id":2013558,"id":"Q2013558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caa25092e5fe50057dfd31112f21fdd0547206e3","datavalue":{"value":{"amount":"+0.8433815240859985","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":"Q1680494$81BB6D30-482B-4AB1-B5A1-1DF02511B622","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A refined algorithm for maximum independent set in degree-4 graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_refined_algorithm_for_maximum_independent_set_in_degree-4_graphs"}}}}}