{"entities":{"Q1117255":{"pageid":1128004,"ns":120,"title":"Item:Q1117255","lastrevid":49255606,"modified":"2026-01-06T20:50:05Z","type":"item","id":"Q1117255","labels":{"en":{"language":"en","value":"Finding a minimum independent dominating set in a permutation graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4091563"}},"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":"Q1117255$C0C95D28-6A7E-4969-9408-9738BF05AA97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9adb9f9840488fbbb6fd64ed782dd3cd63c47bf9","datavalue":{"value":{"text":"Finding a minimum independent dominating set in a permutation graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1117255$B2F4AD25-B394-46C5-A2C7-4823581746A2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"10a5a7c3a7dad196d6cd5fb8dd2d93703e8f6599","datavalue":{"value":"0667.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117255$C3217F20-17B8-4426-88FF-5F60665C5CBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f63572d001dbf2cde0f6a733da367be1a62ed3f9","datavalue":{"value":"10.1016/0166-218X(88)90064-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117255$CB22C56A-B301-4FCC-8AD5-8C97125CF285","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54db673cbb28bd82524949973025fcdaf1d3af32","datavalue":{"value":{"entity-type":"item","numeric-id":522962,"id":"Q522962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$4AD1ABCA-576C-4013-A425-DDFE7ED31D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"63167a25d65d1f693080e69c66ad781938d6d6ef","datavalue":{"value":{"entity-type":"item","numeric-id":802883,"id":"Q802883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$03735B7D-7E02-4692-992D-4D7762EE0AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4c9be9ca23a2d959da50f0057a270a7fbc59409","datavalue":{"value":{"entity-type":"item","numeric-id":170450,"id":"Q170450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$A3981BE3-1EAD-4D36-A493-8AF9190807F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$E9A80FA8-D24F-4500-95C3-09D0C7300104","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1117255$1D6F88CB-D0DF-4EEC-9BA4-ADEA3FB2FE69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de965690d45676042a6ceb139c6d7546600f721f","datavalue":{"value":"1985, \\textit{M. Farber} and \\textit{J. M. Keil} published a paper with the title `Domination in permutation graphs' in J. Algorithms 6, 309-321 (1985; Zbl 0598.05056), where they studied the problem of finding a minimum independent dominating set in a permutation graph and where they presented an \\(O(n^ 3)\\)-time algorithm. The three authors of this paper study the same problem and succeed in giving an O(n \\(log^ 2 n)\\)-time algorithm by means of a linear time reduction from the problem of finding a minimum independent dominating set (MIDS) to the problem of computing a shortest maximal increasing subsequence (SMIS).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117255$0A9C86C4-15AF-4FE1-903E-F955DCEAA475","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117255$6A452351-5113-4EBE-81C4-5EFAAADE1AA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7f354323b7c4988513946717e923778a0ec7b3e","datavalue":{"value":"4091563","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1117255$2D017BE4-7B75-42B9-97FA-890BC024087A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"698781d268edcb63d1ab410f032a99be2b03acba","datavalue":{"value":"minimum independent dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117255$9FABA03B-6E5F-4A9E-9B0B-4F79BEF39462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1117255$DE9C8D2C-9DCB-418F-906D-3F3570D637A0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a200e532179097c3984cb26070785e6c5a816453","datavalue":{"value":{"entity-type":"item","numeric-id":1169468,"id":"Q1169468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$1A1E14F4-AA91-4CCB-9404-25D9D18AC71B","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":"Q1117255$64EE0FD6-C52A-4839-BF13-894727D3CD81","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$8C646CDA-8AF3-48F9-A68B-1E00732EB2D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45bd11f1675efb8493ca16666b6e6674ba98a633","datavalue":{"value":{"entity-type":"item","numeric-id":1161300,"id":"Q1161300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$68502051-920E-405E-9974-1845792EBBCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654247b383091678755541cf2da8e26416bc2e13","datavalue":{"value":{"entity-type":"item","numeric-id":1140430,"id":"Q1140430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$5DC30754-0A51-442C-8CBE-E57E0CB29FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$7298CC2B-45DD-48B9-9746-0E44884A8CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1117255$40667093-64DD-4CD4-B56A-273BCC0D1A83","rank":"normal"},{"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":"Q1117255$9DA2D79F-A028-4A4B-B065-7FE26319FAE4","rank":"normal"}],"P1643":[{"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":"9927b749822ba3f258d84a5125f3524890d9bf82","datavalue":{"value":{"amount":"+0.8316196203231812","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":"Q1117255$C0377CA4-BC2E-4125-A565-2761A069E8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49b2d867b34a21159578a4f11ae4cbf4a9b87c18","datavalue":{"value":{"entity-type":"item","numeric-id":4218434,"id":"Q4218434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e48ff51c72d69f469ab3b7d9e568b6e50e260e9","datavalue":{"value":{"amount":"+0.8316195607185364","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":"Q1117255$D8810DEB-C0EE-42BE-A27C-C8E3DF7F57E1","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":"9768cf42c688b332f722d8f2ab7ac55d04a36310","datavalue":{"value":{"amount":"+0.8244479298591614","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":"Q1117255$F3114C43-47D4-414F-8E51-6507041D8AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6663fb96ef195415af9cf0e3bb8c0cecd2b058a","datavalue":{"value":{"entity-type":"item","numeric-id":1566569,"id":"Q1566569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcaee64e4ea501382d49124724470e3164460ca4","datavalue":{"value":{"amount":"+0.8243347406387329","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":"Q1117255$F9492728-E5C1-4AE7-BE93-F5DC77D8877D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b15c385203aebd77a69e599a03bad814dafa21d","datavalue":{"value":{"entity-type":"item","numeric-id":2366239,"id":"Q2366239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90307370962ce3cb050a066b7abdfc4e3270e05d","datavalue":{"value":{"amount":"+0.8153036832809448","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":"Q1117255$6FCD3EA3-51D2-4673-9A15-580DF4F9A15E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1117255","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1117255"}}}}}