{"entities":{"Q1969940":{"pageid":1980682,"ns":120,"title":"Item:Q1969940","lastrevid":47461849,"modified":"2026-01-01T19:45:23Z","type":"item","id":"Q1969940","labels":{"en":{"language":"en","value":"Finding edge-disjoint paths in partial \\(k\\)-trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1417529"}},"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":"Q1969940$FA94B881-E0C6-4815-979A-8489FB860BD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8b94f8c2b10fa72c3db28013dfaa566ccc682032","datavalue":{"value":{"text":"Finding edge-disjoint paths in partial \\(k\\)-trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1969940$7AD174EB-40E3-477A-AFF0-7EC152B66A98","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7cba632f05080ed39ffe3ef44ce74377d03b1199","datavalue":{"value":"0951.68100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$F9DF1AD5-0B54-4D76-9ADC-BC5FA010D1FD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969940$5D922A0C-84B9-4BFF-B5A1-B6ED6DACE82A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969940$6AC1B218-AD2A-4304-8587-BA26998EA211","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1969940$D1DAB683-8DF6-4485-9E44-B5F39FF648BF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1687a135ab6cd1bf2150f4783b156a6af3bf3bd2","datavalue":{"value":"For a given graph \\(G\\) and \\(p\\) pairs \\((s_i,t_i)\\), \\(1\\leq i\\leq p\\), of vertices of \\(G\\), the edge-disjoint paths problem is to find \\(p\\) pairwise edge-disjoint paths \\(P_i\\), \\(1\\leq i \\leq p\\), connecting \\(s_i\\) and \\(t_i\\). This paper gives two algorithms for the edge-disjoint paths problem on partial \\(k\\)-trees. The first one solves the problem for any partial \\(k\\)-tree \\(G\\) and runs in polynomial time if \\(p=O(\\log n)\\) and in linear time if \\(p=O(1)\\), where \\(n\\) is the number of vertices in \\(G\\). The second one solves the problem under some restrictions on the location of terminal pairs even if \\(p\\geq \\log n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969940$A5E5F865-E32E-48F7-8563-DD48BF8457F6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"094d61d1ff99e208b2511ef0c6fc952ca4052a28","datavalue":{"value":{"entity-type":"item","numeric-id":230778,"id":"Q230778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1969940$CF3A9E8F-7DC0-4742-B00B-CE55BB966F63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$585C36D7-0293-455F-9938-B667A5DF1C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$9D22EA60-46A5-4B13-AFDF-991DB25C3C11","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6cb4fb9e35bdf44a3cb469a54a4e8d88f357d33","datavalue":{"value":"1417529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$AB4F376A-14B4-46AA-9BAB-5332643AAA10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7832632c39185d9554b5fc9078d102748d811215","datavalue":{"value":"edge-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969940$74638FF9-CC1C-4E77-80A1-20118DCF2235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211a09b137bdf42f268c86e50a34a0d25fd19aa0","datavalue":{"value":"partial \\(k\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969940$12AF8D6F-3573-4C49-A75F-88401D91699A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969940$CEAD43CD-2C72-4DAB-A904-0ACE9C6B85F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1969940$F15FAA2F-C3D3-47A8-B04A-7757016D5DA6","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":"Q1969940$806EE731-A55B-477C-9DF3-9953C1380526","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b949f7f46057bfe827cd11d0da4ddad5d921fc9a","datavalue":{"value":"https://doi.org/10.1007/s004539910002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1969940$EDF6A989-6AC0-4E75-A201-1C73D3EB7DB5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"29e96aed4be84077dcd68614cc24b26368582361","datavalue":{"value":"W2046202598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$E00513AC-6512-4D2C-81B7-4EF5E3A4E853","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ddc375b0b4fc448000ed968e1b70244d240d50d0","datavalue":{"value":"10.1007/S004539910002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1969940$7717FE94-8AB0-4261-BF1D-B047E9319B6B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dffc0e0215a981f145f324ec62c077f821b26fb8","datavalue":{"value":{"entity-type":"item","numeric-id":6487440,"id":"Q6487440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9373b91b15d7fc2dd19ae5253dfcbe83c55c6a8d","datavalue":{"value":{"amount":"+0.9745575189590454","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":"Q1969940$92F08D2E-489E-4CFA-BE73-4012403CBC1B","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":"9d96dab2e43353a2cf36c72f4177d4c02295ce50","datavalue":{"value":{"amount":"+0.8436921238899231","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":"Q1969940$F7B58F36-EDB6-4D9F-BB30-1653845CE09B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7de81f579e8c33f12280249135697d0e15a6a3","datavalue":{"value":{"entity-type":"item","numeric-id":4845143,"id":"Q4845143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea1be2c5704ef98211008c17d217ef5a372d4681","datavalue":{"value":{"amount":"+0.841334342956543","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":"Q1969940$546B0661-7563-4B11-A52C-2076EEB7A197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44ff9dc5e76fae62214d37a8b470404c22292964","datavalue":{"value":{"entity-type":"item","numeric-id":3295274,"id":"Q3295274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f24d20d1579bd7a16c398b7e471eacf49115a72e","datavalue":{"value":{"amount":"+0.840475857257843","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":"Q1969940$D50E1B37-772A-4146-B71F-C139BAA2CE9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbb7fc699ba6cba99d0b5f2b785c583cc7ab79c2","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7adf665cf87ac6235d275910ffdef5473cdca87a","datavalue":{"value":{"amount":"+0.8314587473869324","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":"Q1969940$631A6CC0-D27B-4777-AB6E-F10513B82CE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1969940","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1969940"}}}}}