{"entities":{"Q3082912":{"pageid":3093627,"ns":120,"title":"Item:Q3082912","lastrevid":85722122,"modified":"2026-06-03T11:17:26Z","type":"item","id":"Q3082912","labels":{"en":{"language":"en","value":"Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5867673"}},"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":"Q3082912$79E64095-4791-46DF-B45A-F99D9BDA23F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1b6d08ba0202ec1161a9d0de965cf1da7c64a351","datavalue":{"value":{"text":"Subexponential-Time Algorithms for Maximum Independent Set and Related Problems on Box Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3082912$964132A7-DF64-404D-A057-64A898D6E5F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ac77750d2ca58104d3ef53e016bb3eeabf946d54","datavalue":{"value":"1276.05117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$D524C5F7-779A-4733-AAE3-AC39102DC95D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8168c9bcf212cd883c5317f0315132a7176f88c","datavalue":{"value":"10.1007/3-540-45071-8_7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$BD3A987E-21FC-418B-ADA8-09C7995D92AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c7172c45b4ad83fa5382554162a7acd589c0249","datavalue":{"value":{"entity-type":"item","numeric-id":835019,"id":"Q835019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3082912$7B149C7B-253C-4F0F-990B-B2230E1670B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3082912$FC4EF5BE-E838-46C1-BA78-EC85F2914AB7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3082912$A3354C54-B1D7-4894-A45C-C79F93B771D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"491e77b99273305a3a3bbdb2dd66a2b0304c39fc","datavalue":{"value":{"time":"+2011-03-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3082912$0C2774CD-9FDC-4736-BED7-C8616F0A3AAD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$1B0E6C44-2C56-47BD-8CC6-69B1A7F2D960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$F91D2771-8D22-4CB0-948A-966010A949CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$BB2AED98-DF2B-4DBE-9E1E-58F9F9E0A356","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac8e054f7ef5f433e119101d4ca7606b5afd2dba","datavalue":{"value":"5867673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$F422EB9F-B403-4A14-8B27-D3B9ACB3E2DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18303ffb98ab8017b398188f215c19bdb78ecfb","datavalue":{"value":"box graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3082912$0CFA1D9E-4040-40D8-9935-E544BFF4F40C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa507d0c7e77eee2c199431f4b5ef06bc609867d","datavalue":{"value":"orthogonal rectangles","type":"string"},"datatype":"string"},"type":"statement","id":"Q3082912$36A60DBB-4582-48F6-8BF1-90522D15617E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232465a4b21b2442783eb000a1c43840a0e6c26c","datavalue":{"value":"maximum independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q3082912$274DFF89-C08A-4D27-8918-9988B9DABC6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a66c7dccee1dbf664d4d36ea5ef666241879a87","datavalue":{"value":"minimum vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q3082912$BBB8D3E6-D0FF-4874-A435-6097FABDCA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe3411401f8447861d4a95d207cb857c241eb56e","datavalue":{"value":"maximum induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3082912$45FDECD0-9D17-4061-B85B-E99761F6CEF6","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":"Q3082912$CB5F5251-CBA2-47FF-9F8A-7681D9461C68","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba52545704bb2f4c34289c9f35e6ed02efdb46b8","datavalue":{"value":"https://doi.org/10.1007/3-540-45071-8_7","type":"string"},"datatype":"url"},"type":"statement","id":"Q3082912$11D11B35-43CF-4306-889A-D4FA174CBD47","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14aabdf00547a2f39b016ad63cec2461df2f8432","datavalue":{"value":"W1761251274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3082912$7C14C39F-FA56-4422-AF87-931829E1731B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44a8acbc6b8a07e4054fa6f3bb8965ec492c6c58","datavalue":{"value":{"entity-type":"item","numeric-id":835020,"id":"Q835020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adbeeaf39e6e212260bb78b92c5878a156bcb13d","datavalue":{"value":{"amount":"+0.9426135420799256","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":"Q3082912$5429C434-0AB4-46FD-A935-149A6A8D34E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93fb74441ce6b05fc6210e4254ad6692f300bb81","datavalue":{"value":{"entity-type":"item","numeric-id":5434452,"id":"Q5434452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64228d2cd5b3685072179d878564c09e2edaf4b4","datavalue":{"value":{"amount":"+0.8314797878265381","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":"Q3082912$C9EB17A9-8535-4293-85CC-E4D13704C39A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf67c63c91a94aefeb6904c40925557a65c04703","datavalue":{"value":{"entity-type":"item","numeric-id":2921679,"id":"Q2921679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5379e4e6da95ff704cd9fa585d1e5abc5a18c6c","datavalue":{"value":{"amount":"+0.7810114026069641","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":"Q3082912$74104042-D413-4E45-8B21-F5047EC9B020","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ad9b34bbbe8831c5acc74a7e02dadebe0452646","datavalue":{"value":{"entity-type":"item","numeric-id":5454268,"id":"Q5454268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1eb1f52fa49956e70c39d9cc9d3a116f71a1a2e","datavalue":{"value":{"amount":"+0.7735923528671265","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":"Q3082912$820B6B92-3026-44AC-BBDB-05BC962BFBE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed994221465bc78c0414225f61cc260dee94580f","datavalue":{"value":{"entity-type":"item","numeric-id":2403797,"id":"Q2403797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c72dd2ad441bceea7ad4abb68fa247cb4223da70","datavalue":{"value":{"amount":"+0.7629342079162598","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":"Q3082912$C38304DE-2A1D-4D4F-B9FD-F0EAB4E1879B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Subexponential-time algorithms for Maximum Independent Set and related problems on box graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Subexponential-time_algorithms_for_Maximum_Independent_Set_and_related_problems_on_box_graphs"}}}}}