{"entities":{"Q1098313":{"pageid":1109065,"ns":120,"title":"Item:Q1098313","lastrevid":66126204,"modified":"2026-04-12T07:43:31Z","type":"item","id":"Q1098313","labels":{"en":{"language":"en","value":"Parallel recognition and decomposition of two terminal series parallel graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037243"}},"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":"Q1098313$E4715B12-C270-4291-AB57-A49711752DC4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f681554f326c9a657a81b8870598f0566f8cd24","datavalue":{"value":{"text":"Parallel recognition and decomposition of two terminal series parallel graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098313$368294CB-3F2E-42E2-A9D6-662AEB24FCF9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"685ff5b8277ba1064609b0639ee377ec86ced2a4","datavalue":{"value":"0636.68090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$32AEBD51-D3B4-4AE4-83EF-32FF5E162680","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d57242456ee7316a101720cf0c3dc53fba64c87e","datavalue":{"value":"10.1016/0890-5401(87)90061-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$5E291CBD-A04D-45A5-80A9-B0166A198437","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5e3e4a8492e84e11f7f67bea925623ed4dc895c","datavalue":{"value":{"entity-type":"item","numeric-id":237645,"id":"Q237645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098313$A98B07A9-802D-4C2C-B38A-4E290BF663F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9859a4dcc00fc8d1566f43eb1abbd6d402c90633","datavalue":{"value":{"entity-type":"item","numeric-id":751803,"id":"Q751803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098313$3190419B-1AE5-43C4-A04F-6846B72F1916","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098313$113F086D-F0FA-4568-9812-43C1C8E8AB51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1098313$54A31D5C-97CA-434C-9F41-E66D30B54641","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6fb2bd142a9d0f10b14549878b83ff624483c426","datavalue":{"value":"In this paper, we develop a parallel recognition and decomposition algorithm for two-terminal series parallel (TTSP) graphs. Given a directed acyclic graph G in edge list form, the algorithm determines whether G is a TTSP graph. If G is a TTSP graph, the algorithm constructs a decomposition tree for G. Some interesting properties of the TTSP graphs are derived in order to facilitate fast parallel processing. The algorithm runs in \\(O(\\log^ 2 n+\\log m)\\) time with \\(O(n+m)\\) processors on an exclusive read exclusive write PRAM where n (m) is the number of vertices (edges) in G. This algorithm is within a polylogarithmic factor of optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098313$EF3BA4CD-B1B7-4EB7-8147-7AEF01D56CFF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$B1846452-BB53-46A8-90A4-7C6E4E70D7A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$5B07368F-05EB-4124-B665-B8F1FC4C8E15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1166bb6a4ae70050547e833c5685fd9ec002a513","datavalue":{"value":"4037243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$50333446-6E55-42CE-81F0-28AD1C25CFA8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67eedfd8a91af71084560283e50deb4268a6e01d","datavalue":{"value":"two terminal series parallel graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098313$BA00E17B-BE49-4888-AD63-E2E1775B2F93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098313$2EE32518-3C73-4C20-A692-90DCB0079098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5ca7553590ed1fa1bc930967051ac059fc7cf9a","datavalue":{"value":"acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098313$CC7B2714-CDEC-4F90-80F1-F5736F18CF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27b165df2258dd8bf28387bc30a9861fff701afb","datavalue":{"value":"decomposition tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098313$12BC81D6-8184-4FBE-A17C-ACE4848CF1F4","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":"Q1098313$EE4015EC-D5DF-4D52-8982-DD1184806D4A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8939b76dd90409db50b8d3f6f2ade3dcd78f76f0","datavalue":{"value":"https://doi.org/10.1016/0890-5401(87)90061-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1098313$488721E3-E2CF-4E11-9C8A-409A767885AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"578925c59210737f9cb9ee1bdafb4b7abee3df8f","datavalue":{"value":"W2030429378","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098313$4B0F0DD2-5B73-429B-A00A-4744E3F6719B","rank":"normal"}],"P223":[{"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":"Q1098313$EEE86797-B5A9-475F-99D9-A2314EE59318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fe0b762ba59e21ab429837d2d6d47161fd5d6c","datavalue":{"value":{"entity-type":"item","numeric-id":4151722,"id":"Q4151722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098313$A40495C9-BC07-422A-9ED3-F661CB42D3BC","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":"Q1098313$60E71548-0EDB-442B-871C-658C2BB5AB95","rank":"normal"}],"P1643":[{"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":"ae18dcf2d3f796bf8ee7055bc436a8475d66e6c6","datavalue":{"value":{"amount":"+0.8784066438674927","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":"Q1098313$4219460A-C6AC-4194-ABEC-E94175FD1E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b55c346cbad37c64ad2f639e8e162ea799e0b42","datavalue":{"value":{"entity-type":"item","numeric-id":4489178,"id":"Q4489178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c8c820fde5dceeea132cb92a9fa34ace386d695","datavalue":{"value":{"amount":"+0.8767333626747131","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":"Q1098313$A42ABF46-3D5F-47FF-B4DA-3DC1C90E152A","rank":"normal"},{"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":"a214ca41f2a42efeff2ebde5939077aa54fd62dc","datavalue":{"value":{"amount":"+0.8748090267181396","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":"Q1098313$854260A0-DECF-4F88-ADAB-DB5F57CB8273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa7691853dfcf94235517e00bf83f860c0a4a6b4","datavalue":{"value":{"entity-type":"item","numeric-id":1201288,"id":"Q1201288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c81b385a7873e55d33c01fdfabf2b131f56c504","datavalue":{"value":{"amount":"+0.8651009202003479","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":"Q1098313$82AC4698-988E-4A65-9414-C92DFC0639F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a7fcad9700625326b701c62d5c8f00d96e105ff","datavalue":{"value":{"entity-type":"item","numeric-id":5712868,"id":"Q5712868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84040459ab24d6aa5b8030c4814c551895c5eb40","datavalue":{"value":{"amount":"+0.8609043955802917","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":"Q1098313$333DC5AA-C06B-4B0A-8FF8-2FC0B67EF822","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel recognition and decomposition of two terminal series parallel graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_recognition_and_decomposition_of_two_terminal_series_parallel_graphs"}}}}}