{"entities":{"Q1892832":{"pageid":1903574,"ns":120,"title":"Item:Q1892832","lastrevid":46391526,"modified":"2025-12-24T16:55:11Z","type":"item","id":"Q1892832","labels":{"en":{"language":"en","value":"Graph minors. XIII: The disjoint paths problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 767681"}},"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":"Q1892832$F7368969-1C48-4507-8000-FC03BB85F150","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"15497018beb2ed94375e1cbd4f9837a9d4da7c08","datavalue":{"value":{"text":"Graph minors. XIII: The disjoint paths problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1892832$2600867E-A4F2-44C9-A740-78499522D323","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0139394e10d568cfecfbe82d3dfa7767056a87fb","datavalue":{"value":"0823.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$0D57560C-2DDA-422F-9C3C-79068A122C7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdbfdb659d9aeba37340367b24592700a75b41ee","datavalue":{"value":{"entity-type":"item","numeric-id":175487,"id":"Q175487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892832$5878F8E1-AC0B-48AA-A665-CAAA858FA3C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892832$43151F3C-4281-4357-A69B-EF9307C3E990","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892832$19F4C3B1-1C63-43EB-A047-EE922A2D2844","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89939404571a8a457f4efe42bf31156c65cd7105","datavalue":{"value":{"time":"+1995-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1892832$4115AADD-66C9-4F7B-A3AA-7FD737013A19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4eb02fa75e029f5cba15e4255e276cb8be40ad0a","datavalue":{"value":"This paper continues the authors' landmark series on graph minors. For a graph \\(G= (V, E)\\) and vertices \\(x_ 1,\\dots, x_ k\\) and \\(y_ 1,\\dots, y_ k\\) in \\(V\\), the \\(k\\) disjoint paths problem is to decide whether or not paths \\(P_ 1,\\dots, P_ k\\) can be found so that \\(P_ i\\) is a path between \\(x_ i\\) and \\(y_ i\\) so that two distinct paths \\(P_ i\\) and \\(P_ j\\) are vertex-disjoint. It is known that this problem is NP- complete in general; here an \\(O(v^ 3)\\) algorithm is developed to solve the \\(k\\) disjoint paths problem whenever \\(k\\) is fixed. Consequences for finding subdivisions or minors of a graph \\(H\\) in a graph \\(G\\) are examined.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892832$13D565F5-292B-4B53-857B-E82923ED226A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8ba0869bc4942831c8669ed75022f72a56f93072","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892832$71C85D27-5866-483C-B31E-B7C8725B91C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$B96F9693-7527-45E9-8C4D-3294E9EEFDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$63F67AA7-0197-43FC-A261-16529F51B720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$C0662129-E7A0-4A54-9072-17ACE7C1BD37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$8505ED41-D445-4C84-8FB1-10ACEA73911B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e69e5e2b58b4341355c7f32688073b51ad9683a","datavalue":{"value":"767681","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$1697C82C-5ED0-48C8-8C9F-3B0C1B1E1365","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892832$D62BCEA5-88D7-441A-92E9-BECA91C28955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7eb167212c5e4dcc74025cda99a8f41c3ab3063","datavalue":{"value":"disjoint paths problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892832$83403A77-B117-4741-A59D-3E2A405BF038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892832$645B8810-9065-43A6-8CF4-BBF72229799C","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":"Q1892832$7E6F7D33-7C2E-4B76-824A-35A9FD84BDE5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"66fcd69cfe0a14bc61b26978def5bb396631a3d9","datavalue":{"value":"Q55881137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$8203FCFD-2C02-46A2-BC27-E27BA32E2321","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4fc4c3ded45b1a9e4aeaf78ae22427d58babefb9","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1892832$0D89D76D-EB9F-442C-A873-F922E57B7DDE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b0ed837301239e4a42c55cd8e58896c587568287","datavalue":{"value":"W2005079828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$881B617C-1AF9-4F9F-86D0-9B2578A09CA1","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"808254d5f32736926611f36ea8ea819b5a6d6561","datavalue":{"value":"journals/jct/RobertsonS95b","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$0E9CAA18-D264-43A9-A3DF-F26C67A93E06","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38199582dc4f2fa6f739571a11e64adee54ee87e","datavalue":{"value":"10.1006/JCTB.1995.1006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892832$60A284D6-25D6-4DDB-8A20-3527CCDB3193","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca7cd0b5abb3d84144761701e349ba80236b0b0f","datavalue":{"value":{"entity-type":"item","numeric-id":3972953,"id":"Q3972953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c756847eeffad8bc99083ed8db83b3d5e75cf9c5","datavalue":{"value":{"amount":"+0.8926176428794861","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":"Q1892832$F07BACD4-2029-4173-B5B8-DC9E7C6FF159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6f90606216f21b6a05b7eefdd5ba4d7a36b6fc4","datavalue":{"value":{"entity-type":"item","numeric-id":3679228,"id":"Q3679228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d15b8ad4c0a301c75f9633df2a627a3e7adb5e51","datavalue":{"value":{"amount":"+0.8816156387329102","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":"Q1892832$0600B893-1E60-465B-B1E6-1BC8D54FBF94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55b55177ea8384e89f961717617a37b951a104ae","datavalue":{"value":{"entity-type":"item","numeric-id":412168,"id":"Q412168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4e89f1c84422a92024bb0eb1b3591f0d95cd907","datavalue":{"value":{"amount":"+0.8719671368598938","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":"Q1892832$00780CE3-9F70-4ED5-8780-33DEB18C2F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"172d3d8dcff5644feb470680a43687276d8101d0","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9369bd17c892cb23e1f4aacfd3c3d43d0e4a1747","datavalue":{"value":{"amount":"+0.8649880886077881","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":"Q1892832$B59BAB2C-EBAE-4DE7-B54F-5D44629D222C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1892832","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1892832"}}}}}