{"entities":{"Q2629773":{"pageid":2640516,"ns":120,"title":"Item:Q2629773","lastrevid":57965616,"modified":"2026-04-03T06:42:18Z","type":"item","id":"Q2629773","labels":{"en":{"language":"en","value":"A note on the complexity of computing the number of reachable vertices in a digraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6601515"}},"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":"Q2629773$D07049D6-B369-4B20-9F72-0E100166CFCE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eed8f11b31ec784d99524071070fdc9a87ec6a95","datavalue":{"value":{"text":"A note on the complexity of computing the number of reachable vertices in a digraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2629773$D5F011D4-2122-4BDF-84C3-82D6622B3655","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6997dd5f5025b512f21883be1e107fd670de326","datavalue":{"value":"1362.68099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$17FAAD9E-772C-465B-9C9B-5D1C05173259","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98a491cf401843e824e74c863df9e32eb9f67039","datavalue":{"value":{"entity-type":"item","numeric-id":737084,"id":"Q737084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$E2BA06DF-0EDD-4B0A-9CE6-1682B046751F","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":"Q2629773$012FEAC5-4293-4CBA-919E-0864EEDEBF2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"83a193227d6ba6906cd45e4bab84652b56c48091","datavalue":{"value":{"time":"+2016-07-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2629773$F3311C2A-FAD3-4C9C-BA2B-1AC9FE2DD55D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c31a899774be9cc88018d740488846b8a30ac90","datavalue":{"value":"https://arxiv.org/abs/1602.02129","type":"string"},"datatype":"url"},"type":"statement","id":"Q2629773$C0588179-DB18-47C9-A568-5FC70EFF11CB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$43D752BE-AC62-4BC8-A537-9AC36F202D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$55FAA1D5-B1D6-492E-8803-47E5F2D76EDC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ed3e22d90bb272df96f4780a9b82057bad2aaca","datavalue":{"value":"6601515","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$5380A6E0-5B97-4924-8B42-D3AB3D2F88A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2629773$52199657-D6D1-40B9-B152-E19E3AE6F994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2629773$0C8CA587-3911-4761-A448-F295F22E427D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6875ec2def16b48a9065ad482b76c42c8d93cde","datavalue":{"value":"strong exponential time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2629773$700855AD-DD61-4D5C-BC20-AABE617E8A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a618b40b0e1c60d8f3695a0363009e29e3d436f0","datavalue":{"value":"reachability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2629773$5ABE5084-4C3A-40A4-B4CB-5BC016F977F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efd6ca2e632b6ca823bc98fefd73c07a1f518da","datavalue":{"value":"transitive closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q2629773$11DCB922-CE4E-4F2D-B027-98A64065C5AD","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":"Q2629773$9AE75F0D-8C4A-491D-BA1F-3CD3167FC7DF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a8fac71e5712b9d54da0ed0c7fa7f7493ba80324","datavalue":{"value":"W2262622716","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$9D01A771-9E47-4ED8-9093-E96FD983636E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0631af1a7d03611006f1e02e6767eeb9549b57ee","datavalue":{"value":{"entity-type":"item","numeric-id":5363057,"id":"Q5363057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$DA9ABEEB-08BC-4E60-AD5C-563901B5CD0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6b7f242d24937bbcdb000517db57a53a3e35f4c","datavalue":{"value":{"entity-type":"item","numeric-id":4575605,"id":"Q4575605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$F9BACE87-2BC4-4DF8-8529-970D7019AAF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d72a926ee1823df1941e14c10b12be1badbee4bb","datavalue":{"value":{"entity-type":"item","numeric-id":5167729,"id":"Q5167729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$83D045FD-A768-4E77-B3B6-B659FD3AF522","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ba94800656d2c84e9cbeb2260cb47b1cb65809","datavalue":{"value":{"entity-type":"item","numeric-id":3521912,"id":"Q3521912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$7CAD51EA-5FC7-47AE-B079-E62C9D33A164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc0294409be4427cdeb49dc59aae21e2d0aa5f65","datavalue":{"value":{"entity-type":"item","numeric-id":737085,"id":"Q737085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$FA109B70-6B0D-4AAE-A484-8DC05231E282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c38893c344074ea5f04fbd20c01df79bc08fad4a","datavalue":{"value":{"entity-type":"item","numeric-id":2347002,"id":"Q2347002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$644677E3-E0C3-458B-BC17-C7FB998FB44C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a4c23b508911cd4dee06950b209c7fd3b1801e","datavalue":{"value":{"entity-type":"item","numeric-id":3656852,"id":"Q3656852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$2AB45537-A046-4706-8945-C46D560A3272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$E5D00C62-FF62-488C-9707-9772CCD78F95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84ed68bb82322138e41236c78cc7522d16decb13","datavalue":{"value":{"entity-type":"item","numeric-id":3452408,"id":"Q3452408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$875A85C1-EB68-4616-9578-DE959829446A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4226e3e65547158ea8072512457653ecc8bcdac6","datavalue":{"value":{"entity-type":"item","numeric-id":5417690,"id":"Q5417690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$BB5F74BD-9D13-4437-9913-2D4F0A0F6208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4675fdb0e0708f4f0cc371668bf4c2847e859377","datavalue":{"value":{"entity-type":"item","numeric-id":5495822,"id":"Q5495822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$0EB1A2FB-89B1-4C0F-86C9-A6F29965BE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003bc6c20bd1d8ced7d2a1dc42f1b9c84a55618d","datavalue":{"value":{"entity-type":"item","numeric-id":4397004,"id":"Q4397004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$01536B5D-459D-44C9-B84B-1D52893680B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf6a72a62eb7ac00a65cb3378a54949f41ee0676","datavalue":{"value":{"entity-type":"item","numeric-id":2581276,"id":"Q2581276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$6B8DC234-024E-4EE5-A9A3-8E983A661A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7100b8d425431552f17a98423766cda45222cb3","datavalue":{"value":{"entity-type":"item","numeric-id":4625648,"id":"Q4625648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2629773$79132A8E-A77F-4B3B-989C-9ABC6990B70D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"96f44521c8d13d758d6ead4b490e60ec3c267759","datavalue":{"value":"10.1016/J.IPL.2016.05.002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2629773$766A20EA-3818-48B4-8702-4FA8E39CD43C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90df2368e86d12209807df55c22f899bda92f517","datavalue":{"value":{"entity-type":"item","numeric-id":2032176,"id":"Q2032176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a8f55b37c185f8e339dee9e774cdd2468044b6a","datavalue":{"value":{"amount":"+0.8512585163116455","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":"Q2629773$3B5A2581-BB68-4449-B7CD-1D2AFF7B92FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ad82f4540181c2cc4fcab16eda8976c919f85f2","datavalue":{"value":{"entity-type":"item","numeric-id":1384531,"id":"Q1384531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"828fe2c3769ed88f300ef167634bd1d19eaece97","datavalue":{"value":{"amount":"+0.7528782486915588","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":"Q2629773$230C765B-6DF4-4690-BC12-22D3D4D20C69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c1e0b251b3ee582bde7b2244c591e787899b32","datavalue":{"value":{"entity-type":"item","numeric-id":1339381,"id":"Q1339381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1398060d56671b432e73c0a844c2ddf372f5c016","datavalue":{"value":{"amount":"+0.7368555068969727","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":"Q2629773$DA2B43B5-D1F1-465A-B92A-DB7F97E62B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24956dcc6ebe5e428327c416007cbcc8ea403f65","datavalue":{"value":{"entity-type":"item","numeric-id":1323330,"id":"Q1323330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0afc74d8fc716aedd7c5b2769469da92f0105334","datavalue":{"value":{"amount":"+0.7128701210021973","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":"Q2629773$D37E73F6-E638-4682-A6FD-0DE879F1378E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11566476f4a7b622528046c3682334265dc94b8d","datavalue":{"value":{"entity-type":"item","numeric-id":4808678,"id":"Q4808678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83a234aa716487ccd84bb92fdf433b31410bab6d","datavalue":{"value":{"amount":"+0.712196409702301","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":"Q2629773$5F282B4E-C660-4C04-ADBD-58A8F6F60F7F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2629773","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2629773"}}}}}