{"entities":{"Q2574326":{"pageid":2585069,"ns":120,"title":"Item:Q2574326","lastrevid":48596329,"modified":"2026-01-05T08:20:22Z","type":"item","id":"Q2574326","labels":{"en":{"language":"en","value":"An efficient PRAM algorithm for maximum-weight independent set on permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2230521"}},"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":"Q2574326$312DCDC5-718D-487C-9C79-D038EA0F5DFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cc35aac8f72f285d836a0c95898868c0a53187c7","datavalue":{"value":{"text":"An efficient PRAM algorithm for maximum-weight independent set on permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2574326$2FF861A3-B3AC-4F5E-AC8A-7BA0DB2AA105","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c1f59fe716a3a596349e6824d6aa9997f54581c0","datavalue":{"value":"1082.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$4D4F2BDD-7E71-44F1-9C7B-A261E4E305CD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d3d6285857106af452018ef857551601621c0fc","datavalue":{"value":"10.1007/BF02935789","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$DE45A78D-FC41-477F-9E82-90C97ED462E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb7fae79f0b0ff774b380ca7314ec10246657d34","datavalue":{"value":{"entity-type":"item","numeric-id":881881,"id":"Q881881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$1158BAF8-E640-40D3-B729-841E9BCDDBF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"129c1274b58ea0d36e8ffb4cb7701f96a7a7e865","datavalue":{"value":{"entity-type":"item","numeric-id":174580,"id":"Q174580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$22BA94A4-0DEA-4076-A6D3-AB69BF1A2C32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd1454c83476a617e37c60a7911da86eef2fc982","datavalue":{"value":{"entity-type":"item","numeric-id":1590796,"id":"Q1590796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$66683C9C-E5B1-4343-934A-8B4FB4DED3CF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e69251ac594e715cd30473d60ecf4960f751c916","datavalue":{"value":{"entity-type":"item","numeric-id":295417,"id":"Q295417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$D24F663C-79DB-4677-8AEB-8F9B8ECA36F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1d71c893c02f81a63d982851a405419536f9ca4b","datavalue":{"value":{"time":"+2005-11-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2574326$2157C5BB-5A03-4862-A5B0-2704F332FC2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eed7e5f2fe1309be031b8896f6a7119040baafde","datavalue":{"value":"The authors present an efficient parallel algorithm to find a maximum weight independent set of a permutation graph of order \\(n\\), which takes \\(O(\\log n)\\) time using \\(O(n^2/\\log n)\\) processors on an EREW PRAM, provided the graph has at most \\(O(n)\\) maximal independent sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2574326$42A18C73-6FBE-4F31-B683-33036F8B1FBE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a65d3702174a536f0cf916db67d42643a023895","datavalue":{"value":{"entity-type":"item","numeric-id":186197,"id":"Q186197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$0D17BA52-12FE-4681-9A7A-7BAB367B6760","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$1E47A13E-C824-42D2-B86E-AF6D892C0E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$BE6A3E7D-B3D1-4427-AB09-8A8E71881EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$7C2B7539-2B92-456F-B5B7-D5ACA67D3A4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f267b0e148b8bd468dc0c1d781fe7c7b45fb8cd1","datavalue":{"value":"2230521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2574326$997D26B1-D94C-45C8-BB11-17618C04F3E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e63305dac19ff8dc197cda884cf509dfbf6b7c4c","datavalue":{"value":"Parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2574326$CCF16625-F5F8-476D-80E5-57E3C9BCE9FA","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":"Q2574326$5793D511-8C3F-420F-871C-BC179AF8B835","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd59b3f7879978c28db11d989fdb4678ebc0fc04","datavalue":{"value":{"entity-type":"item","numeric-id":4944662,"id":"Q4944662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$4EE8AD07-DD8D-43F3-B999-91C05C601DD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53132a7439025838c534c2eb3f034baeec857b83","datavalue":{"value":{"entity-type":"item","numeric-id":1178197,"id":"Q1178197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$37A19AA6-3B83-4526-84B1-4248206C3DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0a53be4930face860a5a9e9bb129140cbe337db","datavalue":{"value":{"entity-type":"item","numeric-id":1195486,"id":"Q1195486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$3A551DF1-2587-40DE-9A0F-6B9F7C11F008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c5a96890a21e10169edc66df7fd407f84f079a","datavalue":{"value":{"entity-type":"item","numeric-id":1825647,"id":"Q1825647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$4F7C3066-F002-46CA-B550-DBEFBCF99B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$60D6BA5C-9E27-4BD1-89E5-EC18BC715FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$F9CE690B-2893-4EEF-A4FA-0D19DD593532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$A5DF9855-E085-404F-9572-C2E6843587A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b986d7f0a33567a0c5f0358eaad8592b1a1263a","datavalue":{"value":{"entity-type":"item","numeric-id":4240618,"id":"Q4240618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$95B2CC63-F8B5-43C3-A1F1-AF99F7C7AD5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6f513cf72b16a3e9529112e1482e69dd6b9051d","datavalue":{"value":{"entity-type":"item","numeric-id":5931033,"id":"Q5931033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$C6DF9121-7E65-4AB9-B09F-48D557260008","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd590b98335212c805ab70b790bb3bd2f7ff2a8a","datavalue":{"value":{"entity-type":"item","numeric-id":916397,"id":"Q916397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$C340CE39-D6EE-450C-B5CD-B0239853EFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56e15b6b0172983b7e885e1dd10a8b4df1c8f4bd","datavalue":{"value":{"entity-type":"item","numeric-id":4718828,"id":"Q4718828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$3B9A6728-C59E-49CF-9274-3A429B0570D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ffda6579a0c4432812833884be5ec95a34cc94e","datavalue":{"value":{"entity-type":"item","numeric-id":1398021,"id":"Q1398021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$A627EA14-F55A-47F3-944E-4367083AB00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f47a47aee9f2e9d14bb34a2b56769250240026ca","datavalue":{"value":{"entity-type":"item","numeric-id":4454318,"id":"Q4454318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$7ECAAD3A-CF72-4C4A-B556-EB598166A107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f10e7aa27622c2b330946fe327b5b31fbc04f95","datavalue":{"value":{"entity-type":"item","numeric-id":2710758,"id":"Q2710758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$D34CDE73-8921-4B32-B997-2B33682FA413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f04d3e111003ec0246ce1fc0651b2d1560faff5","datavalue":{"value":{"entity-type":"item","numeric-id":4392327,"id":"Q4392327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$CC05966B-AF20-4EAC-BE77-7215C21CC01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a295d22188430201240affd5e5731e578cc1d99b","datavalue":{"value":{"entity-type":"item","numeric-id":4222504,"id":"Q4222504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$2A6C93FD-7BAB-4333-BF26-A9C29D1932AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e79cd44cdfaa5209212dab9de2eaaf98751424d","datavalue":{"value":{"entity-type":"item","numeric-id":4467342,"id":"Q4467342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$C48D0A6A-8999-4F4B-87F7-EDA4756C44FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c79d6645999ab6c1334d7ccf879bcbcc3adc6c","datavalue":{"value":{"entity-type":"item","numeric-id":1195927,"id":"Q1195927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$F70D4309-E779-418C-B09A-2F11C7F072B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f070af4d3f1323916516daea6bfb310091a1086","datavalue":{"value":{"entity-type":"item","numeric-id":1210310,"id":"Q1210310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2574326$AAEA55BE-7AB8-4103-AB44-490076277B07","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3514208a2113fdf58eb8db3dda35fad46899b9e6","datavalue":{"value":{"entity-type":"item","numeric-id":1195927,"id":"Q1195927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dcca9bb66cfd1b0106c3e0609d160e43bcb528b","datavalue":{"value":{"amount":"+0.910008192062378","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":"Q2574326$B1EE1B65-7912-4DCE-BE68-2EC612C33D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63486d3e02b66edbabcdba15c038fbf12a15aef3","datavalue":{"value":{"entity-type":"item","numeric-id":1210310,"id":"Q1210310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ecfdd07e8a2c3e4492e64f6352bd9340baf29cb","datavalue":{"value":{"amount":"+0.90689355134964","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":"Q2574326$55F5A1BE-1B85-4942-892C-14FF07C05E34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a1261909a384312a5610006cec4abfa62b5c34f","datavalue":{"value":{"entity-type":"item","numeric-id":1892868,"id":"Q1892868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30e54aa99c178533b6e4907ac396fa521d08662f","datavalue":{"value":{"amount":"+0.9020934104919434","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":"Q2574326$6629522E-9274-4CAD-B6BF-6F707F9FB586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e3138cc37b7ed9df3db17168ab00f9733f3f9f","datavalue":{"value":{"entity-type":"item","numeric-id":4694725,"id":"Q4694725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"999470105f4913f45e9b83211d88317c0729835e","datavalue":{"value":{"amount":"+0.8967963457107544","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":"Q2574326$A80AEA07-E30A-4536-91A3-B5F5C725B440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2efa3e3d249aec4faea9f01143ba89baad6a0f","datavalue":{"value":{"entity-type":"item","numeric-id":4392327,"id":"Q4392327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"878e6644b9255f0dfb069a5498eb5eea9282e8e3","datavalue":{"value":{"amount":"+0.8389204144477844","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":"Q2574326$CEC80697-5AFC-4D0D-9A3A-66C40E7B77F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2574326","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2574326"}}}}}