{"entities":{"Q1108807":{"pageid":1119556,"ns":120,"title":"Item:Q1108807","lastrevid":66735027,"modified":"2026-04-12T12:31:00Z","type":"item","id":"Q1108807","labels":{"en":{"language":"en","value":"Finding maximum cliques on circular-arc graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068312"}},"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":"Q1108807$2CA8183A-FA92-4C73-90B4-98C33A6F6F99","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a98698a86eaeb452727d2a089b52fe643f0ab9b","datavalue":{"value":{"text":"Finding maximum cliques on circular-arc graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108807$D38F660F-F70E-4306-90C4-DB36127B8134","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f81aba92b4879928aff4fd938161f283905dd6b3","datavalue":{"value":"0654.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$1EB21069-CC2E-4203-8C65-1C0ED4A2A9F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e7e2b3c094108c18a0a4bfaf002640fc6dd1722","datavalue":{"value":"10.1016/0020-0190(87)90007-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$0C5B025D-7E90-4624-BCB4-5239318E1957","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"873796445b5ce8d61b5ea73cdea0956f7aecf751","datavalue":{"value":{"entity-type":"item","numeric-id":294937,"id":"Q294937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108807$478A19C5-D33F-4788-9599-0606C276B703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e72a48c700caa4a7ba5a6fa38f8b3bd5b9ad1c11","datavalue":{"value":{"entity-type":"item","numeric-id":673518,"id":"Q673518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108807$7D5F7935-38D6-4F9A-B8F3-079C360C5B5C","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":"Q1108807$CCDF88D6-55F1-4211-8D68-F3ED7C668D4B","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":"Q1108807$1D711097-52B0-4FDE-9ED8-5979DC82C0B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ed67e8123346b11abce4b1cc7a693a3d473d0b0","datavalue":{"value":"An algorithm is presented that, given the intersection model S of a circular-arc graph G with n vertices and m edges, finds a maximum-sized clique of G in \\(O(n^ 2 \\log \\log n)\\) time. The previous best time bound for this problem was \\(O(n^ 2 \\log n+mn)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108807$E2E841FD-E639-4009-8897-8DE29A004F0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$1613606D-DD27-441E-9231-62857C79BD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$B73A52DE-CF29-4067-910D-FBD53299CD80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b396f85ef7d4d880ade8d64219bf2bca8bebf33f","datavalue":{"value":"4068312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$660BA66C-C49F-4EE6-888B-4F44CE7EEA0A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56f63c03c54600b509ea49738f1b73e83aac9fca","datavalue":{"value":"circular-arc graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108807$8FDE7F1E-5363-4B2D-8A4B-410FAD68551E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108807$58AB0A86-39E3-4F92-915B-858FAF4FD7FE","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":"Q1108807$C340CB82-7D0E-49C7-B21A-6B3AB2B7A3F6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108807$FAE87210-C8AF-4B37-AE7F-EB75BF972493","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":"Q1108807$EAA7612E-0368-4B26-AD46-6A415E34B0CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5c6114b34a23d8cf5b366dc7a7cb2f60d72b04","datavalue":{"value":{"entity-type":"item","numeric-id":3683548,"id":"Q3683548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108807$511E5692-258D-4E4C-95E2-827C3B643E95","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":"Q1108807$6D2C9ACE-44FE-422C-818C-7F1A143B65B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba2a12b9e1e5e9bec0aede63e4f328974ff5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1241058,"id":"Q1241058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108807$60BFE98E-1FCA-4B23-9134-C0F570ABA1AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c77822d433182477ba508eacc0cbb739198c576","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90007-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108807$3442F507-33D6-41F5-AF77-4CFEB6E7AB9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c68c94986741a9ff83cab926a634158fed94f764","datavalue":{"value":"W2113796189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108807$9694311B-2CAC-433C-AFC6-31754D8929D7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8c432b6ad1a1860cfd516d0fda8088bd83021ee","datavalue":{"value":{"entity-type":"item","numeric-id":4373007,"id":"Q4373007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bda8e0c0e6f798e519c5ebf3095e12bd6b43524c","datavalue":{"value":{"amount":"+0.9454602599143982","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":"Q1108807$405C2A7A-A39D-47E2-B968-D2A7AF14053E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3f0f042f3fa408be22b112e81017a0655e31f9c","datavalue":{"value":{"entity-type":"item","numeric-id":3683548,"id":"Q3683548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9e68962059746328fd04d7e698eef93a81512fb","datavalue":{"value":{"amount":"+0.8931958675384521","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":"Q1108807$CFDF18AD-4FBA-4BD0-8ACC-50F282DA0FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"708146783aec21423ea12045ed946a0141fe517c","datavalue":{"value":{"entity-type":"item","numeric-id":911283,"id":"Q911283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd46bfa66e18dd33c5813e62a1bfa4d1fb4dea1d","datavalue":{"value":{"amount":"+0.8912581205368042","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":"Q1108807$19AC2F80-AF47-43C0-A813-793F69F1098E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dd0f6c0e20bc40915520b2b5ceca056c309deb5","datavalue":{"value":{"entity-type":"item","numeric-id":3347925,"id":"Q3347925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24f65672e26cba248b57b140301be927a52f2eb6","datavalue":{"value":{"amount":"+0.88675856590271","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":"Q1108807$7345C06D-42E9-4690-8FA4-1773936C3AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b058145b10d3aaebe767066040c99ee87b9857b","datavalue":{"value":{"entity-type":"item","numeric-id":4385200,"id":"Q4385200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3e79ad63d960cc606647d9940e3c89ce7127e67","datavalue":{"value":{"amount":"+0.8856175541877747","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":"Q1108807$5120F161-C400-46F2-A53E-9FCB527722EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding maximum cliques on circular-arc graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_maximum_cliques_on_circular-arc_graphs"}}}}}