{"entities":{"Q1183585":{"pageid":1194334,"ns":120,"title":"Item:Q1183585","lastrevid":70204923,"modified":"2026-04-13T13:09:11Z","type":"item","id":"Q1183585","labels":{"en":{"language":"en","value":"Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33403"}},"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":"Q1183585$1B67F633-C0FC-4B7A-9418-26459F29F2CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d1bed6afea4c34e26b8323d5b3e01ab7eef6340","datavalue":{"value":{"text":"Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183585$843D7AA1-DB13-428E-ADA8-185FD7E1EF02","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c74e790fc35d956db2b343178ac69beb3c1b8f92","datavalue":{"value":"0752.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$1B474A3F-CF1E-469D-8C1D-062BE1E3A1E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f4acf2731be58bee1a8140fd1ba525746b12dba9","datavalue":{"value":"10.1016/0304-3975(91)90265-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$75C43D3E-BA32-45A7-8C74-3FC9EF6EECBD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$BAADCF90-F4E2-4C6A-81D1-EC2837D7DFB2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$30CAEAEC-4A6E-409A-8695-EC57BC118102","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183585$CBB6E796-18FB-47E9-9BE1-9977F42E107F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f83f067672400fdc9b12f253839c20786cd9f6af","datavalue":{"value":"Given an \\(n\\)-vertex graph \\(G=(V,E)\\), a clique of \\(G\\) that dominates \\(V\\) is called a dominating clique (DC) of \\(G\\). Given a permutation graph \\(G\\) with nonnegative weights on the vertices, the problem addressed in the paper is that of finding any minimum weight DC of \\(G\\). This problem can be solved in \\(O(n^ 2)\\) time and \\(O(n)\\) space or in \\(O(n\\log n)\\) both time and space. An interesting contribution of this paper is that the problem is posed as a special case of a two-dimensional range searching problem. In this way the authors arrive at an \\(O(n\\log n)\\)-time algorithm that uses \\(O(n)\\) space. They also present an NC parallel version of their algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$B324989A-1D15-4FB3-BD13-8EE9AC7ED42F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$5AB34F41-5C26-454F-B399-E1ECFAFCCD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$E54050B4-BAD1-44C7-A4A7-500EF8B689C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$12C2B9F1-BD0F-4839-991E-40FB017B25CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$9D3FD307-8960-46EC-B602-6FCC68570DE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45bf8d541c2a8f142b3e96df00b0ebb3759be361","datavalue":{"value":"33403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$E6828685-47B5-4300-8425-139BBEA12E1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$0684D406-EC80-4071-9A3F-EA9F725E5CAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f0de1c9f116b71d20e00b93e07300eed544fdd8","datavalue":{"value":"EREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$A63C0B82-5CC2-44D4-AD05-98800655C30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$A5B52091-A2F4-4B22-92FA-88A8B99C0206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$3B15CE19-A8DE-42F3-988C-4EBE2A284040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183585$588DA385-441B-42FE-89C8-E78DFE7720E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$7C587E28-9FBB-4AB8-B9B8-5526431F4722","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":"Q1183585$F596E995-B6F1-4860-BAC3-B87F04215586","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd813530b2752f2f9e754dd27abf6a9735ab1248","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90265-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183585$9B10DAA4-933D-480C-A4C2-8392B4E0BB8C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2d4f46d0408de6592c8d393ca049b6a4b046bd9b","datavalue":{"value":"W2043055902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183585$12BA72BF-7FE8-4320-814B-69E0AE0C0557","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d27555288e7eaa496130876ca3decaabfb816ddf","datavalue":{"value":{"entity-type":"item","numeric-id":1115629,"id":"Q1115629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$CCA3CC03-6F2B-43E8-AE69-7F583ABE27D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd3511304867316fbfb65d4b4f901bafb5160d19","datavalue":{"value":{"entity-type":"item","numeric-id":1100915,"id":"Q1100915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$ED0E9060-8F95-404B-B5E6-0B22C4A64B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba9e98d83fb097641689563c120aebf958873f5","datavalue":{"value":{"entity-type":"item","numeric-id":3796769,"id":"Q3796769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$FCCAF4A6-5246-4CF1-8E56-AE993390E8F1","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":"Q1183585$45B833FA-E269-439E-8B9B-CBA6EF32633A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecdacd7d8076e20fd3633d5d758e618af67b3432","datavalue":{"value":{"entity-type":"item","numeric-id":3038630,"id":"Q3038630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$855DBADC-7013-40C2-8202-DAA8D13FFE0E","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":"Q1183585$847F1483-22A7-4508-8293-F6F18EBAFBCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08bbfa2750c080ec67d6b7bc35b58e0a9bc36c96","datavalue":{"value":{"entity-type":"item","numeric-id":3694703,"id":"Q3694703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$3DA01DBB-851B-4C4C-89DB-DC924B055F77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226021fa6dabc2e4cccfdb3df08c02966d9f3e11","datavalue":{"value":{"entity-type":"item","numeric-id":1071505,"id":"Q1071505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$871C1D30-6107-4C3C-98D2-1C1D6B695FA0","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":"Q1183585$78E49B38-9B40-42C9-BAD7-A0D173BBB633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22ab14427184161d4bb538509ec8cb72085e62c4","datavalue":{"value":{"entity-type":"item","numeric-id":1105383,"id":"Q1105383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183585$2A46498C-FD92-433E-9018-9AD413CF8CFD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f3d5551345f7aa308695c08ffc6fc6cf09b9670","datavalue":{"value":{"entity-type":"item","numeric-id":1898177,"id":"Q1898177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fecf1dd727eae475d81f6bd6d5464b9294124b8","datavalue":{"value":{"amount":"+0.8647449016571045","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":"Q1183585$3F1F8D2B-C0FF-4990-9EAD-4EFDE810B11C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14815bc5377a6cb90eaaad1e3dc5919c36e71fe8","datavalue":{"value":{"entity-type":"item","numeric-id":4877526,"id":"Q4877526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a2aeeb83d03ef762bae7c159acba86c58710083","datavalue":{"value":{"amount":"+0.8636821508407593","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":"Q1183585$F015E65D-64DD-4841-A2EC-E1620644E0F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8660c84fc3fce049d9986f0186f2122342711c4","datavalue":{"value":{"entity-type":"item","numeric-id":1100915,"id":"Q1100915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91cd178aeee11fb714f3cb2475e64ce0ce760de3","datavalue":{"value":{"amount":"+0.8636820912361145","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":"Q1183585$542AF84C-6E28-49BB-8891-FCBDAC2B3AF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbe8e572eac38a17a6d7f449ea7ef6dc8efac281","datavalue":{"value":{"entity-type":"item","numeric-id":750166,"id":"Q750166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb60f47cc67e3ef9666c9f66da9fd9a8d58f3242","datavalue":{"value":{"amount":"+0.8466394543647766","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":"Q1183585$B26737CF-A0D9-4FA1-A8B4-87A4B0563068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b886186fef23ef25730caa71fa4d0957c5d84999","datavalue":{"value":{"entity-type":"item","numeric-id":3715153,"id":"Q3715153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10248a981306933e20e98d13c325e76f3225b6c5","datavalue":{"value":{"amount":"+0.8388916850090027","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":"Q1183585$47778941-C5D4-443E-B8CF-2B22DA9B5E5A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_algorithms_for_the_minimum_weighted_dominating_clique_problem_on_permutation_graphs"}}}}}