{"entities":{"Q445249":{"pageid":447016,"ns":120,"title":"Item:Q445249","lastrevid":61922739,"modified":"2026-04-11T02:34:39Z","type":"item","id":"Q445249","labels":{"en":{"language":"en","value":"Length 3 edge-disjoint paths is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6072041"}},"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":"Q445249$ED389CDD-C5E4-4780-9BDA-14874EDF9F38","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6adfc3a5084bceee853e32114eec3d55d6677862","datavalue":{"value":{"text":"Length 3 edge-disjoint paths is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q445249$7794DD45-8F69-44A2-B247-F089F42A7515","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68fcd6755398d16312daba7dc96b5cc3181e45a3","datavalue":{"value":"1247.05118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$474017E9-7BBF-4744-BD93-3B21FBEF7F61","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ae39265b0d6ba138076f4985cf53651a889b602","datavalue":{"value":{"entity-type":"item","numeric-id":321683,"id":"Q321683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q445249$CC3F1FE2-7813-45F0-B234-30C0DFB83DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d62bc6a5494a767ebfa27c0dbd1c58a9b049ca2","datavalue":{"value":{"entity-type":"item","numeric-id":445248,"id":"Q445248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q445249$B982177C-ED1C-4D65-A8A1-8AB662209976","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q445249$5DAE9BEC-732C-459F-8D6E-88B44045797E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f259cf61d7c77bf32ed117699103d184bb54980e","datavalue":{"value":{"time":"+2012-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q445249$157E582A-3D3B-4C19-AB78-F7FB798C94AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c53e77affff58a50fa7d727e08cd93db8adfe308","datavalue":{"value":"https://arxiv.org/abs/1201.6578","type":"string"},"datatype":"url"},"type":"statement","id":"Q445249$F237F729-850F-4AA0-B883-88215948A817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3990c79b1006a37cf3f3818aab58739b019d42ca","datavalue":{"value":"http://hdl.handle.net/1721.1/106920","type":"string"},"datatype":"url"},"type":"statement","id":"Q445249$CF58CC2C-B5AB-4CEE-9FA4-DD396A3FACED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$57E12130-095A-4004-B188-1A4D103F80AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$4B1D0EC2-6FAA-439D-9A90-A232F4153D09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$486EF82E-512B-4622-BA2E-600D2BEF5200","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$D3CA8318-A7AF-4F43-A767-D4AD3BCBB19C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$CC6FA308-A0E8-4A4B-AC8A-A9F1955D195B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36b5121a99c8881b6214619f3c849746789eb64c","datavalue":{"value":"6072041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$84399378-48CC-43D4-81DF-E92A4D90F25E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4caef627bc4e862c1d66a645c7be0a8c787384c0","datavalue":{"value":"Edge-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$9903F175-66B0-4ACA-9113-40C3E9BA052C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$E5E8CEE4-9089-4280-9D63-13BA35749C5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$62C4F33F-C9CE-4880-B1B4-BC88258A3752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9527ea6265f63439699edc7d3ec8cd45a55d81c3","datavalue":{"value":"network flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$E554C30A-7B3D-4972-B24D-EEA94BC1B589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$5786B2CC-B1C5-4FE8-B27E-D6F3E233854E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d88254a5760b31b61e1fb0129d8fa4b56625290","datavalue":{"value":"oriented graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$479FA417-C313-4F2F-9737-57276ADA1EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"583ae4a782a4b0f5bc359c7b8eed7e3d923f41c3","datavalue":{"value":"degree sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q445249$7536995E-9DFD-4A34-927F-6BACFED8806E","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":"Q445249$1459FE7C-A8C4-4295-B92F-C7EEECA1934E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3a04c6810b2dfbd2c8501937510cb2dc73f7758b","datavalue":{"value":"W2075741721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$341EA685-2805-4AEB-9171-382E4C42D911","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4052e065059b9e84cb45ed8fc4702b75d928e0fa","datavalue":{"value":{"entity-type":"item","numeric-id":445249,"id":"Q445249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q445249$82734C6E-19F5-495D-A351-71965F2AD47E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"218c7ef397401dd4ba03dd04bc9ca3fc77192419","datavalue":{"value":{"entity-type":"item","numeric-id":1762664,"id":"Q1762664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q445249$07B7D877-66D2-4640-A06E-B10B894EC76E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8c8a319751de751ab81ab77f24f88c49743d17bc","datavalue":{"value":"10.1007/S00037-012-0038-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q445249$5743CFB2-0723-41F5-B9DE-F2E091F7E403","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f8d7ee34b974bc8121361c2a9a1ea811daddfd2","datavalue":{"value":{"entity-type":"item","numeric-id":1897369,"id":"Q1897369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4b38c06ae6f9331f33e3b3ef3d2fb76a60b6426","datavalue":{"value":{"amount":"+0.8745709","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":"Q445249$8E2DA37C-3C8D-4B30-BFC9-8D6F2B9B4F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbfba2f1b9faf97b69954e4e248f9fb372fd03de","datavalue":{"value":{"entity-type":"item","numeric-id":4249537,"id":"Q4249537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a83082f8ceeee90a7679c4e75b8f9a2062ceca6d","datavalue":{"value":{"amount":"+0.85254496","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":"Q445249$4994E209-2367-4066-B188-6ADE65096523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65eaffef6923d77846421675ebc32cea34aedb8e","datavalue":{"value":{"entity-type":"item","numeric-id":2673486,"id":"Q2673486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ff93153f6778aa8e8dbefd1e47beaba5f51d429","datavalue":{"value":{"amount":"+0.84636545","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":"Q445249$BAEC2577-E456-41CE-8C5E-61595AE72115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5081157046eaed47195f9a54341402ef4321b406","datavalue":{"value":{"entity-type":"item","numeric-id":5954246,"id":"Q5954246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"541f1756d6bfd7f3b43bef2470f5f07637bb8369","datavalue":{"value":{"amount":"+0.84080064","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":"Q445249$D9DB5EED-EA5F-4FAF-9FC5-AAC208B7FA9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dd42f7aa52e4f81a72169dbf1ae755327048cc6","datavalue":{"value":{"entity-type":"item","numeric-id":3455215,"id":"Q3455215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d2ab5e41bb0de7709664aec827adf87613bddd","datavalue":{"value":{"amount":"+0.8404474","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":"Q445249$C1124ED1-B9E1-4553-824D-80582DA87C96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52232b0ce8caaad1f96e521894c2c7083713c572","datavalue":{"value":{"entity-type":"item","numeric-id":429666,"id":"Q429666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c27e88d04bf15df97b687e0c1a0d093e53891b5a","datavalue":{"value":{"amount":"+0.8375568","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":"Q445249$70F3EACC-78D2-4AFB-8C55-BCB59EF7340C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84f9c285951cd661f3ac672ee9d450ee2fd93e95","datavalue":{"value":{"entity-type":"item","numeric-id":3181047,"id":"Q3181047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e841f96515729e08d3242b24181829d356b5b7c1","datavalue":{"value":{"amount":"+0.8373768","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":"Q445249$1C9F9484-A472-468C-9B39-84C4527D1218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9193ee8d05a8bd15e45497e055c7942be53b1b11","datavalue":{"value":{"entity-type":"item","numeric-id":5917535,"id":"Q5917535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d22f6b8ca05f151c42af9dda890cc574d831184","datavalue":{"value":{"amount":"+0.83602273","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":"Q445249$FA7A834F-804D-487F-B5E3-B0E695C162E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9de5b5fa83c084bb2b5f751c5a60890065dcea5","datavalue":{"value":{"entity-type":"item","numeric-id":5890864,"id":"Q5890864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d22f6b8ca05f151c42af9dda890cc574d831184","datavalue":{"value":{"amount":"+0.83602273","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":"Q445249$A218E2EF-822D-4543-9AF7-2BE25C7CEF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9b466f8fbab09290e2f0b436377a826dfaafb97","datavalue":{"value":{"entity-type":"item","numeric-id":3401090,"id":"Q3401090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30a90e0a5436de6ae93873d2099a7b9069387c76","datavalue":{"value":{"amount":"+0.83485365","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":"Q445249$0CA1606A-AD8A-4513-A0ED-2D19C356A762","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Length 3 edge-disjoint paths is NP-hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Length_3_edge-disjoint_paths_is_NP-hard"}}}}}