{"entities":{"Q673069":{"pageid":674918,"ns":120,"title":"Item:Q673069","lastrevid":42635491,"modified":"2025-07-07T12:25:11Z","type":"item","id":"Q673069","labels":{"en":{"language":"en","value":"The maximal \\(f\\)-dependent set problem for planar graphs is in NC"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 985359"}},"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":"Q673069$A8EE701F-8A63-43C3-8EA1-C27FBF5A1E95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9e82f78453de2890bbdf3dd3f53ed3d1b80b8f3","datavalue":{"value":{"text":"The maximal \\(f\\)-dependent set problem for planar graphs is in NC","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q673069$497B6984-86FE-4595-8B25-96A2C0CBD837","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a2607596e1fb0fc0bb4ce41a201b9c524a31963c","datavalue":{"value":"0873.68154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q673069$41E7599F-0859-4B31-9065-F2232490AFF6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d2499cb526bcc1e61375ca5470cba66feb29602b","datavalue":{"value":"10.1016/0304-3975(94)00112-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q673069$3472E0E5-21C5-45E9-BC87-6AF29B1137D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7393b0207d0f3dd972850e1d9213c6ad15bad741","datavalue":{"value":{"entity-type":"item","numeric-id":261380,"id":"Q261380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$E7EA1CE6-C14D-49D6-9D5D-6E2B55AA8E31","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$94E73FB0-E8DC-4237-AB1A-00ADCF777D4F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"00d109e26a7fcb906853bbbede91db350c2b0258","datavalue":{"value":{"time":"+1997-02-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q673069$2EE1CCA0-EAAB-4762-B3A2-9B209F3CBB0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q673069$CA9CF1E9-639F-447B-8375-201DB62A7BD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8046ca86052eb78b9a82b28cb2b260cc7e76db80","datavalue":{"value":"985359","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q673069$706926D9-867A-4164-AAD6-AE578B6E95FF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dadd6a35214eb9708e138da3c7b2ebb146b7a449","datavalue":{"value":"maximal \\(f\\)-dependent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q673069$7DD517D1-A1F4-459F-9BAC-7F6789DBE2D0","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":"Q673069$A75795B7-A092-4C14-AAA0-1AD91F9D59C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"467979d98db9e05ef144a15cc4706cb28b6c2581","datavalue":{"value":{"entity-type":"item","numeric-id":3768419,"id":"Q3768419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$5D6D117D-488F-4DA2-98CA-0B96B68CA764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$ABDB5C03-02FA-4368-9A57-12EF70358268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5fd558c84690f2156ca40543cea731d33b65a30","datavalue":{"value":{"entity-type":"item","numeric-id":3815319,"id":"Q3815319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$DF5B03F7-EAD3-41EC-84BB-FCBE11C9858F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c04a6c63bff4f80cdf6d1fa23c76258296aa2d","datavalue":{"value":{"entity-type":"item","numeric-id":3992991,"id":"Q3992991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$822CEFE0-692D-4AD2-B646-5E4A1CED7655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a83a467a5444a1ba4b7186428b14653739e09ad","datavalue":{"value":{"entity-type":"item","numeric-id":3835033,"id":"Q3835033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$6F39B137-D899-4181-B2AB-400E6959884B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68168df6a65c7efc0077cf652fddf619a3b3d3fa","datavalue":{"value":{"entity-type":"item","numeric-id":4729373,"id":"Q4729373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$E61C665D-522A-4EDA-8544-C9CCED85D33D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b4e3f716bdeb2bf65ab0b9ed3ed663522d44b55","datavalue":{"value":{"entity-type":"item","numeric-id":1073573,"id":"Q1073573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$3EC5F6A7-D615-44F9-9D9B-5E70B0869D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a8b9e919631fd13058b126b3a76e6cf944e4f8e","datavalue":{"value":{"entity-type":"item","numeric-id":1073571,"id":"Q1073571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$0166CE5D-DD40-497A-9069-59F32EA2E54F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bbca1bd52a8b705768d2a03b4b5b5c1b7c0d27","datavalue":{"value":{"entity-type":"item","numeric-id":4385522,"id":"Q4385522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$FF96448E-1D88-411F-A1EC-61E7E74D35D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee77505f29649c24a657424f3dfd6852fee0eca1","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$965CDE17-1A9D-40AB-848F-DFFF14043E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$F5C504A8-9E0A-4403-9C80-A1F6C12D4D1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a5dd87f9b47ea169d77fccc0d3b1ab0e65eb8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3756533,"id":"Q3756533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$A4CD996B-7518-4693-A92D-ACA5E580CEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c6376a0951c753c530d723382cebab9d18dfd3","datavalue":{"value":{"entity-type":"item","numeric-id":4033763,"id":"Q4033763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$4602CBF8-180C-493E-B692-A4A61939CED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23c26fb9669ddefcef70c1e7aa608af69673f02e","datavalue":{"value":{"entity-type":"item","numeric-id":4694725,"id":"Q4694725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$9490E13B-4066-42F1-88D0-D6529E961892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79e10ece143d5f5da20df31acf851dbe1c29d11d","datavalue":{"value":{"entity-type":"item","numeric-id":3662623,"id":"Q3662623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q673069$5E6ED526-2751-4ECA-A0A4-27A6E1AC72E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c96cb94aea3f348a7709c260a2f0ad3afdd8bfe9","datavalue":{"value":{"entity-type":"item","numeric-id":6184372,"id":"Q6184372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa1ba01b446a9aa6bf82276aa7adb5fe1138a884","datavalue":{"value":{"amount":"+0.99530566","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":"Q673069$42F86617-BC4D-48F3-9CE0-1E0A550352FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93f652d2c762f6f68c426726fefe003c77144046","datavalue":{"value":{"entity-type":"item","numeric-id":3599118,"id":"Q3599118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4d9a1cfb4b6cb989c07b6e82e9fbabb0236ab6b","datavalue":{"value":{"amount":"+0.90472424","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":"Q673069$2B12A0C8-4953-4D6C-9362-7FDBEF623D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"380a8f510f1c1a4d059225ab43caa5f8d03ce8d6","datavalue":{"value":{"entity-type":"item","numeric-id":3075609,"id":"Q3075609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bbf532715c6b2874ef5c70c9238016df2ba4200","datavalue":{"value":{"amount":"+0.90432113","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":"Q673069$CF9801BF-FF93-4FC4-99FD-73129B3AA9E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b29bcc688863d5f5869c422bcf44e10cef031fe1","datavalue":{"value":{"entity-type":"item","numeric-id":3834072,"id":"Q3834072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"411e73aaae26a0c7662c8ea0a8ef3c8b3f668d31","datavalue":{"value":{"amount":"+0.8832256","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":"Q673069$D7095151-48B4-4276-B548-96DF6E297F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70db13d89b581d9ae2eea52399c0e5d08e0e5cd1","datavalue":{"value":{"entity-type":"item","numeric-id":834937,"id":"Q834937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1415cce4f8ddacaddaab6f80b2ebd8adc5036e91","datavalue":{"value":{"amount":"+0.87822276","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":"Q673069$5BBA48CA-16FA-4517-BC78-D926EAD18672","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90eba5afcfcbbb2198980dc06173d44d4107ff0e","datavalue":{"value":{"entity-type":"item","numeric-id":2133444,"id":"Q2133444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6bb83642b048540a8016da4002902c864bdbda","datavalue":{"value":{"amount":"+0.8724437","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":"Q673069$C16FE8CE-5819-44D8-B722-F275F7100993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d853b5e94dd9fbbc6c3070b7aaf8954467a5a89","datavalue":{"value":{"entity-type":"item","numeric-id":5301767,"id":"Q5301767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee0b489e6e63c6232aa8f24cbe830c7cccfb5a8f","datavalue":{"value":{"amount":"+0.8702767","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":"Q673069$D5790C3C-244E-49BD-A5BC-E8A64CC18C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc6f83e70f05fe38b9b1d98ab89b50b5661cd890","datavalue":{"value":{"entity-type":"item","numeric-id":3799645,"id":"Q3799645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df585c8019a964c0aa12660c2995251979a4b56d","datavalue":{"value":{"amount":"+0.8672682","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":"Q673069$61881807-033A-44BB-B557-C6A34BD94858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8cabfc266d6542d3370245f6c12b4f6f6aa61be","datavalue":{"value":{"entity-type":"item","numeric-id":3787812,"id":"Q3787812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"520dea67eb83bb0408e96f815bab547e1878f0a0","datavalue":{"value":{"amount":"+0.86667556","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":"Q673069$F50A202C-7349-4201-85B8-BD115B932B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bcb97aca1c0c5105c15caaf11ed180bc94ea650","datavalue":{"value":{"entity-type":"item","numeric-id":3115672,"id":"Q3115672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd5e5938d5915fbd228c249f5b68b7cd64c74bb2","datavalue":{"value":{"amount":"+0.8665096","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":"Q673069$0C167936-C7A0-4862-A54D-550DBC0FD140","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:673069","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:673069"}}}}}