{"entities":{"Q1190520":{"pageid":1201269,"ns":120,"title":"Item:Q1190520","lastrevid":47072065,"modified":"2025-12-31T14:13:28Z","type":"item","id":"Q1190520","labels":{"en":{"language":"en","value":"Connected domination and Steiner set on weighted permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 55567"}},"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":"Q1190520$CD48F836-1E82-41D5-A628-12BED8CDBA60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c22dbbab3f9f228e82b8127453be0f06c6b22ca6","datavalue":{"value":{"text":"Connected domination and Steiner set on weighted permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190520$DABC614F-EDE9-4B02-83C9-193BCBE9D5AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d5f5aeb9aba1904760319cbac68d876910884fa","datavalue":{"value":"0754.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$3670AD65-FB2B-48A1-A2E0-260BCE9231C0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a1e27935b452064fc121218a345e467a2531675","datavalue":{"value":"10.1016/0020-0190(92)90183-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$FACACC19-E8C4-471D-971A-0580402035F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a4ae0f42274118dfca843311517e6e5ee39394a","datavalue":{"value":{"entity-type":"item","numeric-id":1190518,"id":"Q1190518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$CD92628A-87AD-4EAA-BB1B-04259248761C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"92d1037bdd8da0292efc00cb70d39d6f6bf8a1b6","datavalue":{"value":{"entity-type":"item","numeric-id":1190519,"id":"Q1190519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$4CFFC1A6-9AC9-4A4F-8769-205B61533EBD","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":"Q1190520$A82FC98E-0C0A-4565-A033-05EB3F16F361","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d9b40ce89936be2de8343a01d1ced7ff59f76b3e","datavalue":{"value":{"time":"+1992-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1190520$5A29D5F0-BBDD-4733-B868-6A59A987888D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"13d0f2da9ea91fdfc09ea378c035fbe350903548","datavalue":{"value":"Let \\(G=(V,E)\\) be an undirected graph and \\(S\\subseteq V\\). \\(S\\) dominates \\(G\\) if every \\(v\\in V\\) either belongs to \\(S\\) or is adjacent to some vertex of \\(S\\). \\(S\\) is a connected dominating set of \\(G\\) if \\(S\\) dominates \\(G\\) and the subgraph induced by \\(S\\) is connected. Let \\(R\\subseteq V\\). A subset \\(S\\subseteq V\\) is Steiner set with respect to \\(R\\) if \\(S\\) is a smallest set such that \\(R\\cup S\\) is connected in \\(G\\).   Finding a minimum connected dominating set and a minimum Steiner set are, in general, \\(NP\\)-complete problems, but, when the class of graphs is appropriately restricted, those problems have polynomial time algorithms. This paper focuses attention on the class of permutation graphs. The authors improve algorithms for minimum weight (respectively, minimum cardinality) connected dominating set for permutation graphs from \\(O(n^ 3)\\) (respectively, \\(O(n^ 2)\\)) to \\(O(m+n\\log n)\\) (respectively, \\(O(n+m)\\)). They also improve algorithms for the minimum weight (respectively, minimum cardinality) Steiner subset from \\(O(m^ 2)\\) (respectively \\(O(n^ 3)\\) to \\(O(m+n\\log n)\\)) (for both cases).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190520$6B6089AB-9974-40BF-94C9-94D836BFA318","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$414C8866-5C96-475D-90C4-746C3E111190","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$01DD4311-A220-4272-80B2-41618F75C724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$AE3F6D36-5271-4C3B-9E4B-4DBF3B4BF74E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"79b404f20e50109f47b0e8dce3d933672b2393e4","datavalue":{"value":"55567","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$6484C3F6-445C-4FE0-B08D-CA262B0B0221","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b80b546c98a652151eb90e18b150dcaa6fc6300","datavalue":{"value":"connected domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190520$306E628A-B92A-4496-AFA7-8B42EDDD7EA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fc54704482786a243d74572043041f6021b7d02","datavalue":{"value":"Steiner set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190520$C0969E35-B7EE-472E-B40F-36E948A59956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b76fa3d776c7aec425b831d8e742b4ca9e62030f","datavalue":{"value":"\\(NP\\)-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190520$6C00D55B-60E7-4832-B2EB-4471435972E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190520$E9E57516-D600-4116-A90F-19894C1C9C58","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":"Q1190520$92E9DBAC-348F-4DE3-A960-3B2E09A22D01","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d129206c6157a67ab5c7c27b50ddc822bebc1d","datavalue":{"value":{"entity-type":"item","numeric-id":1111388,"id":"Q1111388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$C7734519-616E-48BF-BBAE-E17A4235D25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5f52e309359b78a163c61f97a76c6a6ce5a5096","datavalue":{"value":{"entity-type":"item","numeric-id":3792718,"id":"Q3792718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$45E323E8-BDE8-4352-BCC0-4FAD3C752E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d9f85721316998e076d068f9cd340fa441b494","datavalue":{"value":{"entity-type":"item","numeric-id":1174135,"id":"Q1174135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$2EF93FAB-7C62-4D8E-A573-2C24720902A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c697be7d2af4a6938c4026417e7bd5fd666f7fbf","datavalue":{"value":{"entity-type":"item","numeric-id":3791188,"id":"Q3791188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$00AAA2DF-2247-492B-B01F-B5E60D0C52BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$AC05B204-859D-4898-B729-573E3DEF9661","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":"Q1190520$7B424761-3482-4307-99E8-B0C6C3BA5F84","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":"Q1190520$D5706607-270E-4198-9AA2-3123D24C44D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ea2af1a8c93ceb977d8f389518ef463650adb3","datavalue":{"value":{"entity-type":"item","numeric-id":3823808,"id":"Q3823808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$34733213-4C85-40D6-B695-0DC80672DB43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9d006ba4b2d397812b9353164a360251d8f97e","datavalue":{"value":{"entity-type":"item","numeric-id":3701460,"id":"Q3701460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190520$F586570B-7F72-42C1-9A21-F674E2936A14","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"174e3e89a8acfac36b9adbeb84460a9e80bc303a","datavalue":{"value":"Q126388057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$1E0C36BE-D21B-4EE3-AE85-38FF6783201B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2c002ee37ce849b348ff51811b5edfc4c3746bac","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90183-v","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190520$AC3FDCCF-594E-45C4-BDD4-17ECE6CE2754","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a7f4f3edd8261808fcd5d6a348c44a8ad7d151b8","datavalue":{"value":"W2057476713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190520$F8608CD5-B963-4CB7-A8A0-6F5634B4D226","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3e246c82fb2d25e68c571abf1694ec7890cca90","datavalue":{"value":{"entity-type":"item","numeric-id":1174135,"id":"Q1174135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13d9881ee8f359642e61a0f922da9b03b653f628","datavalue":{"value":{"amount":"+0.9106410145759584","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":"Q1190520$39DF4978-65FD-465E-ABC6-39771C265874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1066561f8185f1bab9d26191f08eb8bafac08c7","datavalue":{"value":{"entity-type":"item","numeric-id":4290917,"id":"Q4290917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0f48e83d1b62c214aebe71ac5ff3034d36d8b96","datavalue":{"value":{"amount":"+0.8748196363449097","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":"Q1190520$8EE163FE-FDFB-4C3C-B805-790230706D43","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":"dd4e6984022fcc7ea9c9b77a2c5d5d0e26a3fde4","datavalue":{"value":{"amount":"+0.8727800250053406","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":"Q1190520$D4FCD3F3-4249-40FD-A709-405FB3726A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1e2fb95d60157c6ef5fe077649a5dc454f6192e","datavalue":{"value":{"entity-type":"item","numeric-id":3701460,"id":"Q3701460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78e15b3966dd3d99d2755c7d4fe13170bb8135ad","datavalue":{"value":{"amount":"+0.8369588255882263","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":"Q1190520$FC30FF92-C695-440F-8647-8EB3F4F33765","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":"3255d0722b5a5717569387ea42e0ea284bdd5dea","datavalue":{"value":{"amount":"+0.8305237293243408","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":"Q1190520$0063196F-5B0F-4167-8A32-AF433ABBED94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1190520","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1190520"}}}}}