{"entities":{"Q5943662":{"pageid":8120464,"ns":120,"title":"Item:Q5943662","lastrevid":47676325,"modified":"2026-01-02T09:57:55Z","type":"item","id":"Q5943662","labels":{"en":{"language":"en","value":"Parallel algorithms for series parallel graphs and graphs with treewidth two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1652498"}},"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":"Q5943662$F52080D1-6FDC-4852-9658-8642F011BC88","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"851b9647cae5a544de4b60ff9199e395c9d163f1","datavalue":{"value":{"text":"Parallel algorithms for series parallel graphs and graphs with treewidth two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5943662$CD1D9DE2-4CB0-44D2-967E-78A9AF486081","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c6cfc8bd0e6e45cee5e8cbb37bf51c6697bf1ce","datavalue":{"value":"0979.05095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$97A4ADE2-863A-4569-B85E-5E7BA0C0680D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"926e613762971a9014a8b1ed071772bdcf0a0812","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943662$00327837-89FA-44D2-A7C9-39CA65A9A40B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a087a3cd7fcac2f206a60f50655d7dfca3587242","datavalue":{"value":{"entity-type":"item","numeric-id":1426683,"id":"Q1426683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943662$268C73D9-1748-44D9-8128-B5FC21C800B4","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":"Q5943662$5D6C530B-20A4-4317-8582-4BE2508B47A2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d99679be6596c8cc4e11d1bbb5f9466f6a2a85c4","datavalue":{"value":{"time":"+2002-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5943662$355B0B03-7E2E-4840-8C38-D1DBD0E40027","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"07c9b0a3e8e046408fc20b2a810144c0d76ca9b5","datavalue":{"value":"This paper improves on Eppstein's algorithm [see \\textit{D. Eppstein}, Inf. Comput. 98, No. 1, 41-55 (1992; Zbl 0754.68056)] for recognising series-parallel graphs. The new algorithm uses \\(O(\\log m \\log^{*} m)\\) time and \\(O(m)\\) operations on an EREW PRAM, and \\(O(\\log m)\\) time and \\(O(m)\\) operations on a CRCW PRAM to decide whether a given graph with \\(m\\) edges is series-parallel. If so, a decomposition tree can be built within the same resource bounds. A graph has treewidth at most two if and only if each of its blocks is a series-parallel graph. Consequently graphs of treewidth at most two can be recognised within these resource bounds, and tree decompositions of width two can be constructed as well. Hence efficient parallel algorithms can be found for a large number of problems on series-parallel graphs and graphs with treewidth bounded by two, including all problems that can be stated in monadic second-order logic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$9AC18C51-34D5-4A15-9343-275D2B0590A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$425112AB-48E0-4B93-8D21-B322144504C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$2A14DEEE-BF8B-446C-AD6E-41A2685CD249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$44BE38A2-E18D-457A-B5B4-CB01BAB76062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$C4B8B5C1-69E6-4DB4-8F72-0DC38319C53A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$4A3ED05C-33C6-42F9-BEEB-AF896388A88E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$EA7E130C-5CAA-460D-9ED1-998060CFA63E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c00a8487b37a57eb02651a10795876da2ec5b207","datavalue":{"value":"1652498","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$33A6CA45-BAD7-457E-AEAF-D1E83FEFDC0A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$06B1CC30-60D7-4A07-85F6-B5B631205ECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$DB537894-7D21-4643-AB4D-D2ED0C7C9253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$172562F3-8E6C-4B36-ACCE-F492B74D4388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28a04a7cb62acb07d997278b9f659c67c89e2b89","datavalue":{"value":"series parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$A384AFBE-29DD-4921-BDAA-75B40EB2C931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211a09b137bdf42f268c86e50a34a0d25fd19aa0","datavalue":{"value":"partial \\(k\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$563441E4-5844-4451-9FCC-794C2BBF7771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5dd8d16b0eb5b7b722b66d8bc1461199fa82519","datavalue":{"value":"tree decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943662$53693719-BD7F-4451-BEF4-6C73499B09DC","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":"Q5943662$21D19206-50E0-45AE-94CA-2D6DD24527CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2987a07c3c241c441ee0b6ef17cdf101957c8703","datavalue":{"value":"https://doi.org/10.1007/s004530010070","type":"string"},"datatype":"url"},"type":"statement","id":"Q5943662$4C0345C9-E17E-40F0-8DFB-DC84146087AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"807f42a71952a8e8d67c909e88d7ef6e7aa3a34f","datavalue":{"value":"W1993522985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$389E68F9-3512-483A-BB35-9E66B02B85D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad79be6d2b3c733e7673b0a3ac9208459bc24e74","datavalue":{"value":"10.1007/S004530010070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943662$E6735E95-AB72-48D0-99F2-DC2FFFCF0B05","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8efa02170e37df3d3802b9f07597086fabc5101","datavalue":{"value":{"entity-type":"item","numeric-id":4373678,"id":"Q4373678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2e3d5cee77ebe88a1f82e9129b6926c5ff8bb76","datavalue":{"value":{"amount":"+0.9287835955619812","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":"Q5943662$D69B09C3-6D0F-465E-ADCF-D05FA3514553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e89f774b938483fca91ceb2b638ab9551f6e5816","datavalue":{"value":{"entity-type":"item","numeric-id":3348421,"id":"Q3348421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2e3d5cee77ebe88a1f82e9129b6926c5ff8bb76","datavalue":{"value":{"amount":"+0.9287835955619812","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":"Q5943662$F6251605-846D-4458-A5A6-A5C4A0C5143B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"153edd1af6381a5f77b38b8b6889f0caa6f48ee2","datavalue":{"value":{"entity-type":"item","numeric-id":4595494,"id":"Q4595494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5671ca5e5127de222c599450ffa89463cc05d23b","datavalue":{"value":{"amount":"+0.9227026104927064","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":"Q5943662$CC0AAD86-F804-426F-9025-C977F6D02FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f5bd9eb33e0c1c6aafa40d7c3549f98b31b84eb","datavalue":{"value":{"entity-type":"item","numeric-id":4210129,"id":"Q4210129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19838a0d33465e68cf39bad38cc457a9d535b2d7","datavalue":{"value":{"amount":"+0.8776673674583435","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":"Q5943662$05131CAD-3A08-4414-8021-5AD0422B3B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d21df1c22cd151da072bd94da5399250b7ca432a","datavalue":{"value":{"entity-type":"item","numeric-id":4645184,"id":"Q4645184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e11494a7f5d940d3a8397de9defab0bc0facf7a7","datavalue":{"value":{"amount":"+0.8776338696479797","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":"Q5943662$C2B39DED-8529-412B-85BD-A8DECFF8782D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5943662","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5943662"}}}}}