{"entities":{"Q4973896":{"pageid":7003475,"ns":120,"title":"Item:Q4973896","lastrevid":58382085,"modified":"2026-04-04T23:39:41Z","type":"item","id":"Q4973896","labels":{"en":{"language":"en","value":"An             <i>O</i>             (             <i>n</i>             <sup>\u03f5</sup>             ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7140849"}},"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":"Q4973896$4DDFB4BE-2DC5-4855-BA0A-B06F2DA49C64","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"626ccd130c3d6a5372278a05a12c2e287daa2a1f","datavalue":{"value":{"text":"An             <i>O</i>             (             <i>n</i>             <sup>\u03f5</sup>             ) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4973896$7E01716E-48FF-4641-87FE-3A0F65AFE7A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa3da7324693dffe297c3f3cdac9a2eb1c57a24b","datavalue":{"value":"1427.68232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$9842273C-FD44-4614-8444-98A9E9F4B57B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1bbaa8d2d782a159aba74dec944629b6b498c56","datavalue":{"value":"10.1145/3154857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$81FC8380-82F0-4733-B62C-A79265FE628C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97be790ad6d0c8ca467e0551a391f0b169da9a88","datavalue":{"value":{"entity-type":"item","numeric-id":2978547,"id":"Q2978547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4973896$14FD664F-8009-42FA-AB01-5E2BAA76BF7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dc8e616d858dd9ff520feda960efa79ad387ec8","datavalue":{"value":{"entity-type":"item","numeric-id":439934,"id":"Q439934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4973896$9222391D-FCF0-4BFA-A5DD-4ED063098022","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"64bbaa3c401dec878328d8d72c14b0373fd9aac2","datavalue":{"value":{"entity-type":"item","numeric-id":92716,"id":"Q92716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4973896$8B5A6356-B908-4CFD-A801-66552E5E52F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"172a3fac4a57b71b2c0e5dd0c89e56be18cd3b6f","datavalue":{"value":{"time":"+2019-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4973896$605EE5F6-B259-4F81-B9A1-B90860495A91","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d691e285c26bdb9a06d3b3f7647358760683d0cb","datavalue":{"value":"https://arxiv.org/abs/1501.05828","type":"string"},"datatype":"url"},"type":"statement","id":"Q4973896$B5FEEDAD-365C-4E62-BAA9-D9961F83C065","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$3D76CE41-D5B1-422A-8CC4-7C0163C1DC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$966830DD-A8E5-4C21-AE91-169785013BCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$541BFDF5-E86E-4627-923F-BCE5617BB4B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9bf18465d7ed04e046bcc9566e8770da97d67ef3","datavalue":{"value":"7140849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$6C818761-4255-4CD5-9114-BA0E3B864659","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95f50a58ef57dac31f2f17ca99a9c4b85ec483eb","datavalue":{"value":"directed reachability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4973896$6F92C6AA-0378-422C-AECF-D1839FE06AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9657d1256537dfba137cf4079eec33317e03688e","datavalue":{"value":"layered grid graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4973896$3FDCA980-5CFD-4B7B-8041-4D3D62A1E93D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7a2d26cf6a3e7ac9220b55c9128399c8a1c6b5b","datavalue":{"value":"layered planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4973896$B1A75C50-1CEA-4005-8F32-44AF31BAFED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e1e89c01692078d552e9dbfa43d9ed6cde94ace","datavalue":{"value":"time-space tradeoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q4973896$288C245A-23D2-428F-BD5A-C9D682F6E828","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":"Q4973896$E1771EBD-76EE-4766-BBC0-860D69806005","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"721c2120b5c28a5b16104ba9a685ed5d3044d380","datavalue":{"value":"W1486144962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4973896$9D8F1F39-B609-4720-A1C2-D48E95B72CC9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d22a3229d7fba1912dee63ae18ef4a66838e5f5","datavalue":{"value":{"entity-type":"item","numeric-id":3459899,"id":"Q3459899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$5969D526-86C0-4796-A21C-8CB9479928A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bfb689fdc7c2d873bcdf3c380066759dc11496c","datavalue":{"value":{"entity-type":"item","numeric-id":2922595,"id":"Q2922595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88dc0b0a747748f8cbf984dfce53f2c62442a751","datavalue":{"value":{"amount":"+0.9563771","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$EFA17A5A-579D-44FD-843F-E5452C6D3C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"649f93494d543fefb4e3d6322b1ce7b5885a81fb","datavalue":{"value":{"entity-type":"item","numeric-id":5875652,"id":"Q5875652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a4a6737afbc4159b3c6db512638a91c73770bf9","datavalue":{"value":{"amount":"+0.89913446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$E4135444-7FF0-4EE9-9499-30213112E2D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06cfd451cf2b37f29e81115849c86d0bce17c36e","datavalue":{"value":{"entity-type":"item","numeric-id":2821694,"id":"Q2821694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5d3adcbb6b19a74acb496598d365ba63aac5d91","datavalue":{"value":{"amount":"+0.88642704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$814B48C6-328D-490C-B118-F008C83D30E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a8a610764103b925ff88626b658b9f1ca737032","datavalue":{"value":{"entity-type":"item","numeric-id":6039899,"id":"Q6039899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0494d80bbb499286806e619f09973b3d8ffd527e","datavalue":{"value":{"amount":"+0.88151926","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$E6541497-7FF5-483D-BCEE-1BB6032DA502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a0a3be3e79c78d7d387f5da02983d4b685ee88c","datavalue":{"value":{"entity-type":"item","numeric-id":5897773,"id":"Q5897773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4f3d2c230a00f946e7a697ec4c1d257ad0d37b1","datavalue":{"value":{"amount":"+0.8763052","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$B126FDDD-B677-4490-B1FB-19F9DC0D62A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12c531765818e839c4578eddd35c4514525de140","datavalue":{"value":{"entity-type":"item","numeric-id":5115772,"id":"Q5115772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da4de175f4d04ee3a9559ea9d9b4f498917f8982","datavalue":{"value":{"amount":"+0.8672976","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$B8D19EDD-020C-4F66-A7BF-A9AC8509D0BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a71418e87d3455875c4603ed2c1b79d98f68f113","datavalue":{"value":{"entity-type":"item","numeric-id":5505585,"id":"Q5505585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39571a906a1156a665be04cd6ab053c7820631b1","datavalue":{"value":{"amount":"+0.8668803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$CAB93C27-01EA-4492-A02A-8D0C73CAC467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2e05189db7c78e8bba797bac01a20b5240cebe1","datavalue":{"value":{"entity-type":"item","numeric-id":2449128,"id":"Q2449128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0996ff46b39030b616e8524274a8cfe814227fea","datavalue":{"value":{"amount":"+0.8638532","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$F1D77005-3B2E-458A-A4F2-6B9FAEC131D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"587605e50028977d297af8a416838286fff1e4b2","datavalue":{"value":{"entity-type":"item","numeric-id":3580968,"id":"Q3580968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d6e032002649e51028f8ef6039de835d7386667","datavalue":{"value":{"amount":"+0.8627542","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4973896$99E8DEBB-AA82-4602-BE4A-A677C16BFE55","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4973896","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4973896"}}}}}