{"entities":{"Q1186160":{"pageid":1196909,"ns":120,"title":"Item:Q1186160","lastrevid":46251589,"modified":"2025-12-24T09:57:52Z","type":"item","id":"Q1186160","labels":{"en":{"language":"en","value":"An optimal algorithm for finding dominating cycles in circular-arc graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36291"}},"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":"Q1186160$56B4D720-C8F3-4B1B-9E2B-2B37B84E0844","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0ca234534876cecc6830739972c05ca3aa0e2c07","datavalue":{"value":{"text":"An optimal algorithm for finding dominating cycles in circular-arc graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186160$7DF7E9E6-B21C-4097-A200-50539610A346","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"706936d5dbe56f7540c00518102212a0d0c3b25e","datavalue":{"value":"0753.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186160$33FE2BA6-8194-4F2A-8764-8837A2DCFCD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c06aedb35861bd0db1324b24fd4fd23bab6f8e4","datavalue":{"value":"10.1016/0166-218X(92)90201-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186160$86165052-3F21-4A0E-AD5C-8A6728A957F9","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":"Q1186160$2A41DE57-0974-4CB9-BF0F-488ABC335827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08fd10dfe7fc8c98a9e2467879f7914a5b87c7a7","datavalue":{"value":{"entity-type":"item","numeric-id":1186159,"id":"Q1186159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$6CF727D4-D49F-4C2A-A3A9-1C0A672CB531","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":"Q1186160$AA7D31C9-8A9E-41A4-A154-52D0CBEEAACD","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":"Q1186160$7F39EA09-6129-43AF-9BCD-934E5756D74F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea01e02cf334682b9d64553e4885e86603802ea2","datavalue":{"value":"A subset of vertices of a graph is called a dominating cycle if the subgraph induced by it has a Hamiltonian cycle and every vertex not in the subset is adjacent to a vertex in the subset. It is well known that the problem of finding the minimum cardinality dominating cycle for a graph is \\(NP\\)-hard, but it is solvable in linear time if the graphs are 2-trees, 2-connected outerplanar graphs and series-parallel graphs. Let \\(F\\) be a family of arcs on the unit circle. A graph, called circular-arc graph, can be constructed from \\(F\\) as follows: each vertex corresponds to an arc of \\(F\\), two vertices are adjacent if and only if their corresponding arcs intersect. This paper presents an optimal \\(\\Theta(n\\log n)\\) time algorithm for finding a minimum cardinality dominating cycle in a circular-arc graph, where \\(n\\) is the number of vertices of the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186160$0054F385-C99D-41AB-AB4E-B17594BE4D8F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186160$EBE73136-E7D9-4316-A941-D50DC460AF43","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"38c952ff8ac57f2b79051b37778c3714b75f99cb","datavalue":{"value":"36291","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186160$384CF45E-268E-405E-A013-BA9B38803D22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186160$582D4666-0533-4326-AAC3-B377C1A86865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"003a1e952d72e825a0c93415549cd7a0c2a0b4cf","datavalue":{"value":"dominating cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186160$AB6E6333-999F-4C8B-89A7-343FC29CC1E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dd24c8e535afc2ed254e200367e4c3db59c5dca","datavalue":{"value":"circular-arc graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186160$D44ADE15-E546-403D-9BEC-6B6B3D6FF44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186160$9B1EBDC9-CF03-4A05-8B03-E01CA0990DA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"07239940f627bb41653311a5b39a7820a8be90f7","datavalue":{"value":{"entity-type":"item","numeric-id":199348,"id":"Q199348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$DAC0DB0B-2F69-4CE3-AA3C-117B249F5A8F","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":"Q1186160$EFB1515C-F7A7-4D26-80E6-F75B20FFAF14","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce3a94db921e6cba7ad432e9dc6feb40cc6db53","datavalue":{"value":{"entity-type":"item","numeric-id":1066921,"id":"Q1066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$135039D7-C1F8-4684-AD57-E3F787E2535F","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":"Q1186160$84822FDA-D9CF-497F-8A33-8267FD065EB4","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":"Q1186160$B1FC6BBA-E5CB-453D-80A7-C9CE82B59E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc63891e4bfc3488caa68ff8e6c76e9b7a919e87","datavalue":{"value":{"entity-type":"item","numeric-id":3684150,"id":"Q3684150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$9E703E9A-CA13-4055-AA6E-0C70A9A8AA1B","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":"Q1186160$0C19E1BE-554C-4243-8FCD-DE0B6587017F","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":"Q1186160$BAD2D974-7159-490B-AC4B-1CCFACFAA398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$ADBB907C-119A-446A-889B-56A39D355D1A","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":"Q1186160$098BFA0A-572B-4963-A00D-7FEA8089A2C9","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":"Q1186160$0B7C13B1-FFB1-49BC-A5F0-BE5CCED2BD50","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":"Q1186160$05851B55-6FF9-4082-B4EC-228686D5D83E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb4098fbc07af19a3657d7d25d62392729a3cf1","datavalue":{"value":{"entity-type":"item","numeric-id":790622,"id":"Q790622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$47215D41-F84E-4BFB-B870-53193B5498B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"136d66374f569c0b8cee662249b6a666e187ddd3","datavalue":{"value":{"entity-type":"item","numeric-id":3870930,"id":"Q3870930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$26F1D87E-D2AA-49B4-90EE-70D8953760DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67963ccb1a867edd78737786aaf07a88d232b3c1","datavalue":{"value":{"entity-type":"item","numeric-id":3933020,"id":"Q3933020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186160$1D5A4909-DF10-4C28-B8C4-6A6027EA5FC1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da94b57125b47af82cf6531a4fc3a272e7219122","datavalue":{"value":"https://doi.org/10.1016/0166-218x(92)90201-k","type":"string"},"datatype":"url"},"type":"statement","id":"Q1186160$A138E59C-024C-4EC5-B393-E0413BEBBED0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fdd0326fa14c01c75c3dacf9c1abdc73884442f5","datavalue":{"value":"W2060722839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186160$4C38264C-471A-4900-8265-AB365C67C21C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb6319b44e48cd1c7b0ef992fcd8dc44945df198","datavalue":{"value":{"entity-type":"item","numeric-id":1066921,"id":"Q1066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d1c303e55734dcd4f46919b387ffc045fd06615","datavalue":{"value":{"amount":"+0.8810040354728699","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":"Q1186160$3AA64C74-3F39-4723-B6ED-723E7843EBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76f9b27cf2cd5c8e07083604b70aa263cfb35525","datavalue":{"value":{"entity-type":"item","numeric-id":4027864,"id":"Q4027864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98ccd7346e23a12c48f4e154a77043cde89e7021","datavalue":{"value":{"amount":"+0.841132402420044","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":"Q1186160$1B6AFE36-FF39-459B-B39C-B21EA8639022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65f2adad166cff9e52331dc53d13c8e8c78ae4ac","datavalue":{"value":{"entity-type":"item","numeric-id":1060966,"id":"Q1060966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d46b46e82e3e715a6a1044ce6cdf79a8c40cf563","datavalue":{"value":{"amount":"+0.8334433436393738","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":"Q1186160$9729CFC8-C841-43C7-811A-1319C928F7FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d8d4ff03475779920c6b0ae09531ebda225e610","datavalue":{"value":{"entity-type":"item","numeric-id":4823301,"id":"Q4823301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c7912c6dc6f0fb10af505827615505e43a40f69","datavalue":{"value":{"amount":"+0.8263034224510193","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":"Q1186160$55A3387B-B134-4C3F-B98F-F7CF8112E13B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1186160","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1186160"}}}}}