{"entities":{"Q1208474":{"pageid":1219223,"ns":120,"title":"Item:Q1208474","lastrevid":47149165,"modified":"2025-12-31T20:24:05Z","type":"item","id":"Q1208474","labels":{"en":{"language":"en","value":"General vertex disjoint paths in series-parallel graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166470"}},"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":"Q1208474$CD101056-77F4-49D6-B390-4330CACD8515","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6cee24a6ade156d8b18ec031873cbc7fcadd9b9","datavalue":{"value":{"text":"General vertex disjoint paths in series-parallel graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208474$C4CED9D6-F66C-4C04-91CA-A94CF1835A78","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8fb39c0cb0cb28d0cd41ef128eed15d157334f78","datavalue":{"value":"0786.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$8E7F5468-4511-4022-A5C6-0885AD47D72A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b286b5c0ba5ca1a7b1d544a4486bbe06f9c9cf1f","datavalue":{"value":"10.1016/0166-218X(93)90035-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$E36BF52B-B846-48DD-B747-B663D96C284A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d049f32d9c5057f44701109662e613026b41055","datavalue":{"value":{"entity-type":"item","numeric-id":216241,"id":"Q216241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$2C4E5625-6C87-47E7-BB20-C7710527A55B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00be9811bf59ecd49d79f72a29ccc16efb1d1aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1208473,"id":"Q1208473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$4BA25E78-BE8B-44A8-BDBB-C96FD807291C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$80867720-5F51-4D86-9E11-5859ED6D28C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208474$F3E9B5FA-DFDF-4125-9F1D-77EAA15C8382","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"833c660bdcfa0da9dd361ffc47c770488ca31aca","datavalue":{"value":"The vertex disjoint path problem is NP-complete even for planar graphs. Robertson and Seymour proved that this problem becomes polynomial when the number of paths is a fixed integer. A linear time algorithm for solving the decision version of the general problem when the input graph is a series-parallel graph is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$B8B13D0C-E4AB-4E9A-9249-0319860775A6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$9BC874FD-6342-4C82-B997-F7DD1B4033E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$B9EACF84-D4EB-432E-BDA7-3380A9B86823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$4163FB0A-9DDE-4AEC-886B-569E18039867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$0C1A3829-9D8A-4E6F-B8A7-6D9FA11E8A89","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04afb5286a763d326c11546e1b53314dc3e6b327","datavalue":{"value":"166470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208474$7BC308DE-DBFE-4ED0-A692-2E5707AA4CC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fa27cadd379f059e18918c4962b6f5cc3628369","datavalue":{"value":"vertex disjoint path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$0D25BEDF-57B3-437A-82EF-043FCAB594FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$31725AA7-2021-4964-A2C9-B20483E84354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$077F38BB-2BF6-4F45-8191-B2E934A7480C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$30E566D2-8EEF-4B35-879C-091DD042EFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb191028560f8580185d25fb1e0694b4ee05dbf4","datavalue":{"value":"series-parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208474$DB498B3F-FCCC-4CC1-AC20-DBEDF2386A37","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d2038bc5b75235dbb16f529946235e1ed908b44","datavalue":{"value":{"entity-type":"item","numeric-id":583878,"id":"Q583878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$E242E42B-72F3-421D-BE82-6D098022D28F","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":"Q1208474$098833DC-C834-4787-AA57-E24CE6730667","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$63139F69-E3ED-41C2-B57B-7617058677A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc69c6156e9471fec17a5d754a7b363dbf0153f6","datavalue":{"value":{"entity-type":"item","numeric-id":3812222,"id":"Q3812222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$54043CFA-5157-4CC8-8545-5874DB660F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$471B0DFE-8C86-47BB-AFAE-DF69E237FF32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$F3B3C022-671E-4A0E-A127-98FCB36EBD09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$420B452C-A139-4EB9-9D3C-20AC64DD14F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae06ace3264ebdef666fd198a2d1441400a748e","datavalue":{"value":{"entity-type":"item","numeric-id":4087195,"id":"Q4087195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$48F4A726-9F0D-40FA-95C3-0387807269D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9d5b23b5f6cd07dffa9f9ed4247b217c1931468","datavalue":{"value":{"entity-type":"item","numeric-id":3679228,"id":"Q3679228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$12B7DDBE-30FA-472C-9216-618DB45C9005","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$1F5BD9A6-5A23-4E48-9169-24118AC5CF80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9cd5ab2b4dcc204e3d6bd923419ed31e399a96a","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$5CB65836-CA0C-46A6-A9DF-826E30435054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6938dba8ab074bb35a73751ce72717af16278b0d","datavalue":{"value":{"entity-type":"item","numeric-id":3972953,"id":"Q3972953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$CBBC45A4-AA23-41A6-BD15-0E294036B88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$7DAF621A-7776-41E5-AF0B-70C6941F0D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32cfb1bd9a2e4985fe859e378e81598a196911d8","datavalue":{"value":{"entity-type":"item","numeric-id":3930654,"id":"Q3930654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$DF914211-2F14-4EF7-956A-36EDA8E2A57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9388ccbe0fa89b8254ed27bf69035ad55de4b6","datavalue":{"value":{"entity-type":"item","numeric-id":3343454,"id":"Q3343454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$1F8135CA-6AB9-4C77-BB25-8389A54049AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$9BB3CE42-A046-4223-8D4C-1FEB5C6DC34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463f0cac3e60d82d492cd248d7fbeefa8310d26f","datavalue":{"value":{"entity-type":"item","numeric-id":1150633,"id":"Q1150633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208474$2123854F-DBD7-4797-8C48-27BFFF536DE4","rank":"normal"}],"P1643":[{"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":"4beba6886272ddcb4d8ead6632f53a08aa791234","datavalue":{"value":{"amount":"+0.8469145894050598","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":"Q1208474$C121F4D1-792C-4B0B-9347-36E40323BAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b617181582622ad0d0ece768db849c9e0182991e","datavalue":{"value":{"entity-type":"item","numeric-id":3503839,"id":"Q3503839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d94fa299f0b897d24ee4f5d6c4f0e77d321574a","datavalue":{"value":{"amount":"+0.8441612720489502","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":"Q1208474$C81E2C23-0623-4D04-B27E-20B8A3609C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3794e2aa554b553087030530b298006877b8ee98","datavalue":{"value":{"entity-type":"item","numeric-id":3211338,"id":"Q3211338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb6c1546813266aa5db9a0562ef6edf182164443","datavalue":{"value":{"amount":"+0.8437097668647766","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":"Q1208474$F6F4140F-4D1C-4AA7-B53A-88EE5B566E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4977730f092ab66be71a6750e73f5fc0033f1ad0","datavalue":{"value":{"entity-type":"item","numeric-id":2367446,"id":"Q2367446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d87bfeeba06d4fa0a0bf60dcd675973fbf861b4","datavalue":{"value":{"amount":"+0.8398053050041199","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":"Q1208474$25A4CD25-7746-4D78-814D-5E19127DCB85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eac0158f72f7b5d30fb3e635fb048c43c6c02e7","datavalue":{"value":{"entity-type":"item","numeric-id":3140410,"id":"Q3140410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00ff0b2ce2dbbc32f14569b0356bd3dc3cc9f43f","datavalue":{"value":{"amount":"+0.8397437334060669","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":"Q1208474$AC6B1F3A-840A-4745-937D-F8FCB0D78831","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1208474","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1208474"}}}}}