{"entities":{"Q1186158":{"pageid":1196907,"ns":120,"title":"Item:Q1186158","lastrevid":69845172,"modified":"2026-04-13T10:43:55Z","type":"item","id":"Q1186158","labels":{"en":{"language":"en","value":"New clique and independent set algorithms for circle graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36290"}},"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":"Q1186158$951AEA3B-34F0-43A0-A397-5DE5921CEEA4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c8f1841f6cc236279bce5e59fa349c0eb70b16c","datavalue":{"value":{"text":"New clique and independent set algorithms for circle graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186158$03DF6450-7D42-493B-9747-8F68E9BCD460","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"153bf53b050f9f2b6fa094b8cdbfeb6d97f9aaa0","datavalue":{"value":"0794.05120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$12E2DF7D-BCFC-4AC3-90F8-31AA19D58711","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c73c85fc5f16c0f8d303a62b0c0ccb389be3a655","datavalue":{"value":"10.1016/0166-218X(92)90200-T","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$DCCF0BBA-7848-48E1-9998-4580983ADB27","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54db673cbb28bd82524949973025fcdaf1d3af32","datavalue":{"value":{"entity-type":"item","numeric-id":522962,"id":"Q522962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$7259DEC0-78D0-4495-83FC-8BF0D62A9DD2","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":"Q1186158$5334872B-8DBA-4EDF-973E-B00D3153ED56","rank":"normal"},{"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":"Q1186158$6657BDB4-7C88-45CC-8BB1-175C13E427EE","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":"Q1186158$2B09FC66-9FF1-4B93-B892-0E89FD2254CA","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":"Q1186158$4F202BA3-AF12-4268-B63D-D4B39B07A4D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"27909cc75323f6be46a0b869e24f9071bec5fa1b","datavalue":{"value":"The authors present efficient algorithms for finding a maximum clique and a maximum independent set of a circle graph. A circle graph is a graph representing intersecting chords of a circle, or, equivalently, intersecting intervals of a line which are not contained one within another. Given the interval model of the graph the proposed algorithms improve over the running time of the best previously known algorithms. If the circle graph has \\(n\\) nodes and \\(e\\) edges, then a maximum clique of cardinality \\(c\\), a maximum weighted clique, and a maximum weighted independent set can be found, respectively, in time \\(O(n\\log n+ \\min\\{e,nc\\log(2n/c)\\})\\), \\(O(n\\log n+ \\min\\{n^ 2,e\\log\\log n\\})\\), and \\(O(n\\log n+ dn)\\), where \\(d\\) is the maximum number of intervals crossing any position of the line in the interval model of the graph. Some algorithms solve the problems by reducing them to that of repeatedly finding longest or heaviest chains in suitably defined partially ordered sets. Summarizing, the paper is both interesting and well written, and introduces new techniques to solve the problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186158$352A8907-4330-439E-9FC3-EAAE92139A5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$0A236A36-3C34-4DF9-8D84-8DC9D4B730C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$D7881B21-DCDC-4B8A-A754-9FA3659D03A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$CF9D21F1-FF47-46B1-9AB2-0D922B336619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$FD62878F-3442-4759-9F8A-098A55985CAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11b67a293c62c6fe7752ef02d0ff6bd9d52fed5e","datavalue":{"value":"36290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186158$B1786454-2987-4C8F-9985-66670AC88387","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186158$30AD21BC-842D-4194-B4DC-A8A06F136E74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a181c7b2997b4e3846dd20fd7f7cfe8269ff11","datavalue":{"value":"maximum clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186158$967398E2-86F8-49CC-A849-66FB57FC9BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232465a4b21b2442783eb000a1c43840a0e6c26c","datavalue":{"value":"maximum independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186158$39281164-8E0E-4726-82CF-A2693E975650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a5e1f1191acc6a9fe899dae84da95c86beb92d","datavalue":{"value":"circle graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186158$0CA63806-DC80-484C-8A38-5B44DA6AE9D3","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":"Q1186158$C8E56D8F-25F3-4090-BDDA-93A09F458EB0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$2891E185-D60B-4FB7-81BB-D33FF10B463B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db21cffc9a30e21b6f7d43dc8fec24dc554ce3ce","datavalue":{"value":{"entity-type":"item","numeric-id":1085982,"id":"Q1085982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$BDE91CC8-16AF-4EEC-8817-C7BACF7B1A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$1350A9ED-DE2A-4B2F-B25D-FE2F4BBD02C3","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":"Q1186158$5ECA78D8-7D6D-4816-903B-41413006AB87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c406cccfaf0baf112bd503da4f4373902a51376","datavalue":{"value":{"entity-type":"item","numeric-id":4093489,"id":"Q4093489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$DE647EAE-0459-47BC-A61F-3126C7CA4B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb5fad4a3eeb2a8fa034ee89eddc3861cf9d0c63","datavalue":{"value":{"entity-type":"item","numeric-id":1219686,"id":"Q1219686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$85C8201C-4EF8-47D2-9F62-7F4452FDB0CA","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":"Q1186158$EF512ADD-3237-48B1-A34E-06B725B071E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f171b45557bd6ba2c91d5444caf4ff5931e9df1b","datavalue":{"value":{"entity-type":"item","numeric-id":4067141,"id":"Q4067141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$8F430F5A-5C7E-4A8F-8FB7-0CC864AFF313","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":"Q1186158$83FA30CB-3E64-479A-80FF-78C8B9D406C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d22d1a66627507c9e175f0940657f78d850ce78c","datavalue":{"value":{"entity-type":"item","numeric-id":3956413,"id":"Q3956413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$2E36AB03-A001-4A08-8BF2-09D6C31BE030","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":"Q1186158$985B99EB-43B6-42D5-AA92-6448D3C1C006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4861b889694d4cd2c5f38eb801b0fa0c2924ad9","datavalue":{"value":{"entity-type":"item","numeric-id":4125781,"id":"Q4125781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$3EF9160C-9F0B-47B2-8BA6-9A07E54EF0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b57ae0178b078a7805d69f23f6f3821c98a2cd7","datavalue":{"value":{"entity-type":"item","numeric-id":3673101,"id":"Q3673101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$8A953A04-6E6C-4719-9E70-587E0FCFD8EE","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":"Q1186158$0EFBD2B8-2EE7-49D7-8478-A5F63D3F312F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e04ac7e5cc19a9d877bb6c72ff9a08f51eaa348b","datavalue":{"value":{"entity-type":"item","numeric-id":3910008,"id":"Q3910008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186158$D6ACFD63-592E-4EC6-9D99-B941AF98EEBD","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":"Q1186158$6FE06D54-71F6-42B6-9852-1C428E68E35D","rank":"normal"}],"P1643":[{"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":"fc8c4370ecb900802ad782abbce943476d5d268f","datavalue":{"value":{"amount":"+0.8970168828964233","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":"Q1186158$6A88B4D4-7489-4B83-8245-5C39BF0DFBAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4efb0eb0621cab47ea2ba242b3bbb58a7f7b3d7","datavalue":{"value":{"entity-type":"item","numeric-id":5191641,"id":"Q5191641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a0b0eadf5b17f67b57769a3d523b5e09af3d72e","datavalue":{"value":{"amount":"+0.8952118754386902","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":"Q1186158$512E209A-AC3B-49B4-A89C-C473278AD170","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":"1f8f84c2eba56bd2c9f1e111d3d1c5beafbd0190","datavalue":{"value":{"amount":"+0.8702899217605591","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":"Q1186158$47D0EFB2-E187-4C0A-BF5D-C574D0BF56F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81f8522657c97133be080ce85ab874720ed80f36","datavalue":{"value":{"entity-type":"item","numeric-id":765500,"id":"Q765500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"150b16d8bbdccf136d0d6c7b6132f53eaafb33bf","datavalue":{"value":{"amount":"+0.8586366772651672","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":"Q1186158$107A848C-CD4B-4EF3-B2AF-9C7E8F2FAABA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4046994d70801ada8af81143efeca18d8e0845d","datavalue":{"value":{"entity-type":"item","numeric-id":5406178,"id":"Q5406178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2f802a655c9d5507d1874ae837df06904e9dccf","datavalue":{"value":{"amount":"+0.8529991507530212","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":"Q1186158$CD4ABEC1-E36E-4E60-BC94-988891476492","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New clique and independent set algorithms for circle graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_clique_and_independent_set_algorithms_for_circle_graphs"}}}}}