{"entities":{"Q1100915":{"pageid":1111667,"ns":120,"title":"Item:Q1100915","lastrevid":49154038,"modified":"2026-01-06T16:37:22Z","type":"item","id":"Q1100915","labels":{"en":{"language":"en","value":"On domination problems for permutation and other graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045184"}},"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":"Q1100915$9230E5FA-735F-45F3-9130-2F2CBB882A8C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d5a5429f6d3ff422ef84b8dfe98134aa7329b223","datavalue":{"value":{"text":"On domination problems for permutation and other graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100915$D008FF0F-F0A4-43C8-A77A-D7371AFFE8D5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7777ba170b2cb72767dd4bf5989d4e8f936b8b9c","datavalue":{"value":"0641.68100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$FE2F466C-8706-4003-AFD6-3E9299D64F7A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7ca8ef08da3886902be5215d75fc68b82b6049d","datavalue":{"value":"10.1016/0304-3975(87)90128-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$9147516A-816C-41FA-8984-2BACC0E58B57","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$739A7BCD-540A-47C5-891C-00E093C9CC4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$52E697FC-CA76-48D4-9875-9D4F464CA13B","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":"Q1100915$379CA992-4E14-4ACD-878E-A1BFCA62AF35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1100915$6F3042CD-1B4C-4FB1-BE96-7F5B9E8B1758","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"58a2661c4e725c0af63bc2ba59fa8385c634f7e4","datavalue":{"value":"The authors study various restrictions on NP-complete graph problems to subclasses of perfect graphs. Specifically, the following problems are considered: (a) weighted independent domination problem for permutation graphs, (b) weighted feedback vertex set problem for permutation graphs, (c) weighted dominating clique problem for several classes of graphs.    Polynomial time algorithms are obtained for (a) and (b), \\(O(n^ 2)\\) and \\(O(n^ 6)\\), respectively. In the case of (c), the authors obtain an NP- completeness result for weakly triangulated graphs as well as polynomial time bounds for other families of graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$F0688465-2BF2-4F0D-A0FC-D139F3E25DFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$23D4CB30-61C6-4394-BF30-ED829BFE711D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$2DBD6D8B-6880-4443-820E-E0B208A79DD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b347afa72b4820e0e6a38519070867e7ec21aa3","datavalue":{"value":"4045184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$FFF3C34C-98CC-441B-B264-CB458B775F8A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f8a95c378677359a9c306d83e1204bbd684dc3d","datavalue":{"value":"domination problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$E24F6662-46EE-4ED0-ABAA-53141AD6E7E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$AAFE67D9-75A3-4BD2-964B-72204A9568B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$58E08491-5C68-4CDA-B851-F67869F1A576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$67C72A68-F8A8-4A95-A9C9-194339AF308F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea2fa8c47cec59459fda0a9113d6a429d4f4e013","datavalue":{"value":"Polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100915$84A332D4-6259-4427-8356-A35359E78CD2","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":"Q1100915$0D0137D9-0BB0-4F73-B4D8-629CA1AAEE44","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":"Q1100915$CBE57CA5-B9CA-47CD-8B29-D8AC9D0385EB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3def7c6a858010b9dbd6239e04a97b681ae5ad65","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90128-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1100915$DE3BE88C-0E47-40BB-86B4-FBAADBE8CECA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a858f40d09b6652b7bd6510456f48fbdffd3f1a3","datavalue":{"value":"W2080076699","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100915$A6A51868-C11B-4274-A939-9AC11F8AAA99","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$8EBBE299-5ED8-40D2-8552-4B45A96D2358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74932f79c2ba549ae58af939161b35db92eb95c2","datavalue":{"value":{"entity-type":"item","numeric-id":3694712,"id":"Q3694712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$1306C0E2-EC3C-470E-890C-EA0B11210264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224ad1a17328eb20bf4beee8188b5c55558e4ea5","datavalue":{"value":{"entity-type":"item","numeric-id":1060966,"id":"Q1060966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$54D17845-979F-4331-BDA0-F0480B032CF2","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":"Q1100915$B3CE0648-8886-46AF-B7A8-0F499CB9D912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fdd014eef4c1612ef9474be7d708d46c2a2ce21","datavalue":{"value":{"entity-type":"item","numeric-id":1068110,"id":"Q1068110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$DBF6FD62-F724-4911-802E-2AD0C1D56588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"319fdaa27484a2ebcce1969d012e31307e954320","datavalue":{"value":{"entity-type":"item","numeric-id":5663894,"id":"Q5663894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$CC89BE0D-0280-44A5-A0A4-F0F89170B2BB","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":"Q1100915$9396DD95-6A2B-4F22-82FB-98F31957B3DF","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":"Q1100915$F6181F61-CCCD-42E3-8711-72746B71EB72","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":"Q1100915$FAF31B4F-C9E9-43A4-980C-B95FE6D32C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$C6C8A7DD-3B23-40BA-85AD-916CDF6F1F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f3a345ac969991571213b2a34fe3bc06c137d18","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$7F6ED1C2-5DC1-4FA0-9B72-8E71B820B48E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$CD3647F7-2C0D-474A-8F94-DF4D59E861DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da2d95ac31a70052a778a9e28ab2a7a081f20922","datavalue":{"value":{"entity-type":"item","numeric-id":1092931,"id":"Q1092931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100915$351498CB-76FA-40DC-AE61-380F37F91329","rank":"normal"}],"P1643":[{"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":"261eca1f675997a5cc86d8c3f531d285a5280107","datavalue":{"value":{"amount":"+0.9674633741378784","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":"Q1100915$6FEAAC0C-55F0-4DA1-B150-2F74387FCD11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d97c7cf3c0cd45d6e496534e0d6b0dbaf7b40731","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a799ae68343391e38ed27daf87f34bf4e047dab9","datavalue":{"value":{"amount":"+0.8939083218574524","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":"Q1100915$CA1F57D2-1703-47D9-A97C-D36C725C1E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd20f70d2c33e35ecfacebc69bedec55d7fd6c33","datavalue":{"value":{"entity-type":"item","numeric-id":3694712,"id":"Q3694712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d700ff00c5c6d04ed88fa087c9ac0b982176752","datavalue":{"value":{"amount":"+0.8614065051078796","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":"Q1100915$3AF48488-BC9E-4823-824A-3B928F3FD122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9683a7b50fac958bf57451d45633d3fb8757dce4","datavalue":{"value":{"entity-type":"item","numeric-id":3679238,"id":"Q3679238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a65a8ffa9b9e26c515aaf403dd7c35bb2594dc2","datavalue":{"value":{"amount":"+0.8602274060249329","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":"Q1100915$527238EE-5026-4657-BEFC-DEEE23DFB6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7394aa1e7f4d1c5c45e7c9132e7ae2fe5c7f58b","datavalue":{"value":{"entity-type":"item","numeric-id":4281625,"id":"Q4281625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b240b0bcaf6fac93fb104ab3aeba7d711c346976","datavalue":{"value":{"amount":"+0.8548137545585632","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":"Q1100915$7D40DCAE-55C8-48C8-9537-F76895E11B24","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1100915","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1100915"}}}}}