{"entities":{"Q1339375":{"pageid":1350114,"ns":120,"title":"Item:Q1339375","lastrevid":46360308,"modified":"2025-12-24T15:30:34Z","type":"item","id":"Q1339375","labels":{"en":{"language":"en","value":"A parallel algorithm for finding a triconnected component separator with an application"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 699126"}},"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":"Q1339375$222396A0-8455-41F1-8231-CF189F565D5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8132aff489e6e01ef39a7c9fb424607e20737661","datavalue":{"value":{"text":"A parallel algorithm for finding a triconnected component separator with an application","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1339375$42827986-B574-4E20-B78A-1FC71D44B2E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfe66af6258ded708492c3ed2ff5ec517f4b649b","datavalue":{"value":"0847.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$659EB61A-DE3B-49C7-80E0-9945F6B3AAC5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"375596379175425772813343dfa054d3b55bc8e2","datavalue":{"value":"10.1016/0020-0190(94)00147-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$224B9601-2B4C-45EB-9404-4696ED6659D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7393b0207d0f3dd972850e1d9213c6ad15bad741","datavalue":{"value":{"entity-type":"item","numeric-id":261380,"id":"Q261380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$DE6815C6-2141-4E1B-A0D9-56200110B033","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$18E0ACE0-90B5-453E-A890-800FD903553E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"40eacd21a7efb3a2fa818fc0823bb429dea7c652","datavalue":{"value":{"time":"+1996-09-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1339375$62BA5FEA-13E8-4135-9430-D1501EB0F63C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34b0ce7a75365a44a604e9cfa6874fedf06a5e81","datavalue":{"value":"A separator of an \\(n\\)-vertex graph \\(G\\) is a set \\(S\\) of vertices of \\(G\\) such that the graph obtained by removing all vertices of \\(S\\) from \\(G\\) has no connected component with more than \\({2\\over 3} n\\) vertices. A triconnected component separator of a biconnected graph \\(G\\) is a separator that is the vertex set of some triconnected component of \\(G\\).   It is shown in this article that every graph \\(G\\) has a separator \\(S\\) such that \\(S\\) is the vertex set of either a bridge of \\(G\\) or a triconnected component of some biconnected component of \\(G\\) and such a separator can be found in \\(O(\\log n)\\) time with \\(O(m\\log\\log n/\\log n)\\) processors on a concurrent-read concurrent-write parallel random access machine (CRCW PRAM). This result improves Khuller's result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339375$6D9C6728-FAEC-4931-B418-8739F2E4B211","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$DC7CACE1-69BA-4473-A48C-9091FECED72D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$FBE92CED-94C0-4B82-BC73-4A37A173FF23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$1FE12968-51C9-426D-9A37-ECA70E315D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$EAEB801F-6258-4CC7-88D2-9E397D246E88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db4ef7c7cbdccfba6d3693bb7a3fd105c39a83d0","datavalue":{"value":"699126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$49F10F2B-FCE6-47B7-A511-355D7A61E659","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2048756a75c8d4059ef4461062ea4db6f752f1f3","datavalue":{"value":"biconnected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339375$AFB29F5E-5BC0-4AA9-BF74-5C7906E24E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16382045e0cfe30182ad180ef8d44f60dac5e0df","datavalue":{"value":"separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1339375$B32C1ADF-D2FD-46C3-A8D2-82690BF39963","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"377196f0936f14c5f40316c205cbb7535714207a","datavalue":{"value":{"entity-type":"item","numeric-id":585662,"id":"Q585662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$00CC673A-526E-4349-B3C4-CA03B8881B94","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":"Q1339375$7D507795-9BDE-48AD-B089-51889EDE915B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b2742fea6f2fd89d693c3607052948ca0d39997c","datavalue":{"value":"https://doi.org/10.1016/0020-0190(94)00147-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1339375$17334289-457D-4093-92C6-C2B96BED7B11","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0990dd20e750dae5d1d053dd9885ae2d6d4bc02e","datavalue":{"value":"W1975955995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1339375$B798F7BC-1655-48F7-BD80-BE42DE8D3DF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"491950cd634035e7fd95f4062271456f77492b49","datavalue":{"value":{"entity-type":"item","numeric-id":1062457,"id":"Q1062457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$654ACAAE-6F30-4713-AB84-6B684A68C3D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80231f82b0decd13db206021375ccda945be9d00","datavalue":{"value":{"entity-type":"item","numeric-id":758188,"id":"Q758188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$4FB06377-3797-4BAD-85D0-F0271658194A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d158cc3aa4f838cb96a6d00c9cb7a42742066354","datavalue":{"value":{"entity-type":"item","numeric-id":4202214,"id":"Q4202214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$F38AF8F4-6436-4A16-8EF0-D977869487AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee77505f29649c24a657424f3dfd6852fee0eca1","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$949BFBDE-C4A3-45B3-A6C6-6EF4593D3AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03d22134f08f4b9e10104cfff7b86312799b93d6","datavalue":{"value":{"entity-type":"item","numeric-id":582121,"id":"Q582121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$A9E20F0F-2161-4D17-BCA8-6F2708BF9A8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c6376a0951c753c530d723382cebab9d18dfd3","datavalue":{"value":{"entity-type":"item","numeric-id":4033763,"id":"Q4033763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$13F4D276-A715-4F3A-B13C-A4266BFD8EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$C6D4EE7E-179F-440C-AACC-5D901683A116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d65e5fa96c04c984fc37232aa1378e70a7f1aba2","datavalue":{"value":{"entity-type":"item","numeric-id":1120597,"id":"Q1120597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1339375$43AF1C8D-91CD-4955-96A3-4E949F9A0EC9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1bd77889364dc99e3d4acc3bdf06796df57e71f","datavalue":{"value":{"entity-type":"item","numeric-id":4202214,"id":"Q4202214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40ddeb3b36182f2a88ffdf01fedf69b07a8dcb07","datavalue":{"value":{"amount":"+0.8607000708580017","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":"Q1339375$EDC64873-A616-4C3E-B66C-7BA97F24D2B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c4e4d82c32120c7ff97a9c3a34c07d95de9000","datavalue":{"value":{"entity-type":"item","numeric-id":1193533,"id":"Q1193533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2dc5dddfb2606c2fc0627cc8d47104cef9068af","datavalue":{"value":{"amount":"+0.8542927503585815","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":"Q1339375$472856C7-37C2-44ED-8526-4F50ADDF0707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27fe3af7d370b48b90032be9374eddd63e88677c","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6eefb7d75b905bc77c60af03c9a430512f2454c","datavalue":{"value":{"amount":"+0.813740611076355","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":"Q1339375$B09605C8-6415-4C38-BEBE-63FA00EEB26E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"683558f65ee28addbbff1e08fdfcacc0cd7afe29","datavalue":{"value":{"entity-type":"item","numeric-id":1900892,"id":"Q1900892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f620b2235029ee96dafef0e7ea632cca392ebfe3","datavalue":{"value":{"amount":"+0.8054134249687195","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":"Q1339375$CA07ABF4-6B8E-491F-ACF1-1EBF3384A3CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1339375","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1339375"}}}}}