{"entities":{"Q1209148":{"pageid":1219897,"ns":120,"title":"Item:Q1209148","lastrevid":47151001,"modified":"2025-12-31T20:31:03Z","type":"item","id":"Q1209148","labels":{"en":{"language":"en","value":"The complexity of domination problems in circle graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167439"}},"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":"Q1209148$4FA368F6-4364-45E6-A7A0-55084A88BE95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64662e05be13c7eb4947d0e6fbc02f7c2f433947","datavalue":{"value":{"text":"The complexity of domination problems in circle graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209148$40850E31-904D-4255-9E84-E09F539DC958","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df7c6f150cecfafc0fa2c549cf6299b8248a44e7","datavalue":{"value":"0786.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$E3559DB1-37FE-4831-A9E2-237AE6911AAD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa4bfd490069f6577af73be8c6e0b49b65958af3","datavalue":{"value":"10.1016/0166-218X(93)90178-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$3D676313-17B8-434E-88C5-91BDC913AA22","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"725145adf60736a410a92f7f2d72d3094c36ae9d","datavalue":{"value":{"entity-type":"item","numeric-id":680147,"id":"Q680147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$B3713C7B-3232-48D4-BD9F-75AB540C75AB","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":"Q1209148$F1886FCA-9390-4C20-A33B-870C49805440","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1209148$F23A2F83-682E-4C91-87BB-A40727737FB6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"25d3af2bf035973ae2bf6a593b22d70fb4e7d4a0","datavalue":{"value":"Circle graphs are the intersection graphs of chords of a circle. It is shown that the problems of finding a minimum dominating set, a minimum connected dominating set and a minimum total dominating set are NP- complete for circle graphs. A polynomial time algorithm for finding a minimum cardinality dominating clique in a circle graph is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$456B9372-58A3-45B0-999E-56DF034CC6D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$FEFB4015-A5FD-49C1-BB0A-2A6DAFEF3145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$AD9A8DEA-3421-4BDF-B6DB-DC036165D47A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$0B63DFEB-0745-4375-B30E-6F53F2CE300E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$8EB3AB8D-87FB-4FD8-A192-6078FB1EC06E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b9c2ff95ce3d74dfe54278aeddccbed9088af7a9","datavalue":{"value":"167439","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$2662F541-3D1B-4794-BB70-1307D8861CC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$DEA2B6F5-9457-48D5-BD5B-BC2C817A30CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$09812571-FA07-40B6-B211-DB58B295AEC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$8C091433-23A6-48E9-8623-87972059E3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$1D409329-8215-459C-9CA4-FECABD4BC18E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$C7452DFF-8345-42FA-8276-3684E78B39FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$09402388-48DB-47D5-BF93-5FB5BB6E427D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"338d491e779f9f8fccbfbe82226b1cd8c040d4a0","datavalue":{"value":"circle graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209148$C1859983-0C42-4D3D-ADB9-8FC7994FCF35","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d7b68a7038ced6bb495ee6f40c0c2c6a57863a23","datavalue":{"value":"Q56503307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209148$9D83567A-C993-443F-ADC6-4F6F0D6EB4F1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d2038bc5b75235dbb16f529946235e1ed908b44","datavalue":{"value":{"entity-type":"item","numeric-id":583878,"id":"Q583878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$9F495EB9-3D96-4912-AEE0-75D52106CB02","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":"Q1209148$93B864F9-5FCB-4FB3-9BFB-9F39375FB810","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cad86ad3a1ac50950b1260b4a2c41ef04e6c321","datavalue":{"value":{"entity-type":"item","numeric-id":1117255,"id":"Q1117255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$E4DC63C6-BD2F-4C22-A73E-445AFCEDF688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d207798ab208e2d6135aa6be4f21281e7287368f","datavalue":{"value":{"entity-type":"item","numeric-id":3944643,"id":"Q3944643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$E6255D38-FB30-41A9-BFF8-2B4AC8800173","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":"Q1209148$4E954BBA-83FF-4364-9213-F9771FF2ADA0","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":"Q1209148$639BAEF6-483E-4C0C-A2D1-2521DC1C5221","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":"Q1209148$1BFB62F2-CB12-42F3-B53F-BDAE10F8F210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92112994480729c7855c79dcbbba9d177aba86ba","datavalue":{"value":{"entity-type":"item","numeric-id":3773922,"id":"Q3773922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$542C3C37-4EAE-4C1C-98F4-199060908230","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":"Q1209148$F4F48C99-8724-4AD1-9829-83CC55C9BDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c468deacf9a7ac62a21f4655f39fd612630193","datavalue":{"value":{"entity-type":"item","numeric-id":1174132,"id":"Q1174132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$A6CE3AB8-B8F0-4990-8BEA-26F367926C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7c87567ac1088fdc9bc31fcb5a631f687d94f5a","datavalue":{"value":{"entity-type":"item","numeric-id":4875855,"id":"Q4875855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$CD655D83-76D8-4F1E-B7A7-072C9C60C0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aff4421d83319ba553decf5ffccebfa072fb3c1","datavalue":{"value":{"entity-type":"item","numeric-id":1169487,"id":"Q1169487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$AD5CFF63-B51E-48AA-8546-38FEF380A7B5","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":"Q1209148$38BA9097-26D1-4F7C-99CA-5B6948A2FBC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1e2e6abdbb3a464ba621eca18bcd8f91d2af79f","datavalue":{"value":{"entity-type":"item","numeric-id":4710682,"id":"Q4710682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$9D47C981-8BD6-4449-AC63-8673F398A0A8","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":"Q1209148$70E21B7F-A52F-4C69-A4DF-2B4771DF829A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"329a5de00a7f842ca79da38a1dc02d38dfdd7fbb","datavalue":{"value":{"entity-type":"item","numeric-id":5675749,"id":"Q5675749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$DD9A938B-5DB3-4A73-8A7C-3F05EADE6E51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$20897A72-B6D9-4809-B48E-E99C77E01D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d119bafd326492790771315a712041bc3b44997e","datavalue":{"value":{"entity-type":"item","numeric-id":3782805,"id":"Q3782805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$A5242E30-E73C-4FB0-83BA-D28529B70A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbed46534388845d219f776d9b682225206fcf03","datavalue":{"value":{"entity-type":"item","numeric-id":3136612,"id":"Q3136612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$12C4C6E8-13ED-4B5B-A0C6-DBDAEDC581BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2f7cee5ab9f468b6c01bc006a2b0b5d8926cdb9","datavalue":{"value":{"entity-type":"item","numeric-id":3791195,"id":"Q3791195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$1559578B-63F9-4167-90FD-A9087015A829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0ba1d687a45ea9b6660e43c3eb9d43b1d106ece","datavalue":{"value":{"entity-type":"item","numeric-id":3696538,"id":"Q3696538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$1EA2A20C-500C-4490-A13C-A7E50B14F5FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7837402e24a30593e31f2e5fbca38ca6bffcb66","datavalue":{"value":{"entity-type":"item","numeric-id":3740282,"id":"Q3740282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209148$6A62FBCF-BEB7-4650-B72D-58F7ED9F3912","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"089039d8662e6e17145634f890005e9df0f7b05c","datavalue":{"value":{"entity-type":"item","numeric-id":4511218,"id":"Q4511218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e7374d7310623044854ca76642b3b02fb2bcaae","datavalue":{"value":{"amount":"+0.9111721515655518","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":"Q1209148$A6669D1D-D0EF-4DFF-8D52-2488CE45872A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b15a46b9074cb58b4ca3768666c0e06dd4ad7ea5","datavalue":{"value":{"entity-type":"item","numeric-id":5200517,"id":"Q5200517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"946b09f9c670d92bd9eadbb704971eaa7887b814","datavalue":{"value":{"amount":"+0.8863371014595032","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":"Q1209148$45F225D8-B5A6-4C6B-B8F5-1C1C4051A504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"839a9df83bbfa96829e864b485c42d37c204e81a","datavalue":{"value":{"entity-type":"item","numeric-id":4511217,"id":"Q4511217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b0445f3aa9188f9545bda47fe4ee4691dcbf97","datavalue":{"value":{"amount":"+0.8857622742652893","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":"Q1209148$C8C71E48-F63C-4C32-90D5-B6B61AA99B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b1db6d7d54ea05d9691bbf4ec7604677be6e46f","datavalue":{"value":{"entity-type":"item","numeric-id":4952684,"id":"Q4952684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b0445f3aa9188f9545bda47fe4ee4691dcbf97","datavalue":{"value":{"amount":"+0.8857622742652893","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":"Q1209148$3A9F89D6-6F4C-45A6-AED0-5293B9471419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04705166e114c6e1550610f4bd159b0154dfa3d","datavalue":{"value":{"entity-type":"item","numeric-id":1045943,"id":"Q1045943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7004ef751eb7769a44c52548a583ededbaad95f4","datavalue":{"value":{"amount":"+0.8725128769874573","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":"Q1209148$E6BBA77E-A730-439E-91D1-071E97FCF9B7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1209148","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1209148"}}}}}