{"entities":{"Q1071505":{"pageid":1082257,"ns":120,"title":"Item:Q1071505","lastrevid":48905707,"modified":"2026-01-06T03:33:16Z","type":"item","id":"Q1071505","labels":{"en":{"language":"en","value":"Decomposing a set of points into chains, with applications to permutation and circle graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3940719"}},"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":"Q1071505$84B09DDA-6411-495D-BE84-BF097AA1373A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9202c0ae7fafb865f0af2dc8573253820bdd730","datavalue":{"value":{"text":"Decomposing a set of points into chains, with applications to permutation and circle graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1071505$A6765073-D88D-4236-84AF-DF726CFE70A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7143c39e813bedc10c8c7016d40d2dfcbcab3131","datavalue":{"value":"0586.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$15894CF1-C8EB-42EF-B2CE-E8B4DA8FD6D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e7f4d41ddaa108d4f6b68f9f0c37d3f2c5a831d2","datavalue":{"value":"10.1016/0020-0190(85)90093-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$4A89254F-ADEA-4C9A-8117-8ABCEBBBFA91","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef258125b32d94b9773ef4777eac737975d274aa","datavalue":{"value":{"entity-type":"item","numeric-id":584278,"id":"Q584278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071505$C766BD57-7CEA-40D7-8D76-FF211CC1BADD","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":"Q1071505$4A50C45F-31BD-4463-9D1F-30EE812A2B4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1071505$55BB48C0-61F2-461D-B8BC-0BFE4C6E8B4B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0277649f58547c348b4c40cc8fec3f2c4409335d","datavalue":{"value":"An O(n log n) time algorithm is given to partition a set of n points in the plane into a minimum number of ascending chains. This result is then used to derive O(n log n) time algorithms for a number of problems concerning permutation graphs including minimum coloring - thus improving on the \\(\\Theta (n^ 2)\\) time algorithm of \\textit{S. Even, A. Pnueli} and \\textit{A. Lempel} [J. Assoc. Comput. Mach. 19, 400-410 (1972; Zbl 0251.05113)]. This coloring algorithm is in turn used to derive an O(n log n) time heuristic for coloring circle graphs, with a performance guarantee (the worst-case ratio between the number of colors it uses and the chromatic number of the graph) of O(log n).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$9A127749-8BAC-4895-A085-203EFCD8CA3F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$8BBFCF68-B663-461D-955E-2C8492AF699B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$13508A66-3043-4514-A1F7-AAAFEC38D47A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$B7520AE0-D4EF-4710-8855-7437E86DFA40","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"77cbf90021ee775c08425e6717fa64c052e0ac49","datavalue":{"value":"3940719","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$005E2A25-044F-4C68-842C-7F870EB41A89","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$0DCB3C72-8C25-4A1B-9980-93C805F2570B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$B91BB019-7AB0-41D9-9E43-B60FB4FCBEEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$EECCCCB4-EFB5-42F0-A205-CD584E4C8896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd56a2212a842b6d4d536e6cdfd98611c028566a","datavalue":{"value":"partition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$ABA78B12-0A12-4C0C-9CD0-637F2622C3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96031e15b9c0a855280dd010231908c76a1fe7e1","datavalue":{"value":"ascending chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$CF2B1F5B-D9C4-468C-B642-3AC293FC06EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$566ACC2A-B7CF-4235-A689-713B1E13D8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5488239e8636e5441c28bb41bbc61d2d68332166","datavalue":{"value":"coloring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$A67ECED0-E287-40C4-8646-46F4E82FAD5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"338d491e779f9f8fccbfbe82226b1cd8c040d4a0","datavalue":{"value":"circle graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1071505$CFB250B7-F652-46AE-A6C7-A0BEFE092705","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":"Q1071505$4E1DAED2-EA4E-4F36-A5C0-B99836BB2510","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7c123455c4bb054358aabee19d20fae02d7e42b3","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90093-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1071505$AD0C61B7-95AF-4582-BE6B-B40867D675F4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78b8f6b4db26961d8519f3ac599b763995ac8a80","datavalue":{"value":"W2061944694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1071505$65890853-B96B-4FAE-A016-6D6A6605C182","rank":"normal"}],"P223":[{"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":"Q1071505$81CBA9A5-3E61-462C-A406-9D0D35CE172E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d3feabf7738470c05cc9bc57fe6125054132512","datavalue":{"value":{"entity-type":"item","numeric-id":5684962,"id":"Q5684962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071505$E2848EB7-38E1-49E0-ADF0-44C391CE6D63","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":"Q1071505$DEE868D1-FA1C-4851-8A09-FF4DAE28561E","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":"Q1071505$8A5F49A2-D30B-4AFB-9DB1-B0701A768B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071505$E97D711F-1328-4DBC-B267-CB0408095B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071505$F20B45A2-75F5-429D-BEC4-5084E6B1F97E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8aaede631bfdc54d481cb5dea09d28a4412b7","datavalue":{"value":{"entity-type":"item","numeric-id":3763600,"id":"Q3763600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1071505$72602187-B8F6-41AA-B2C2-58BFA25C3C8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8332693019daf9490f05a08f7d0bc2318590b8d7","datavalue":{"value":{"entity-type":"item","numeric-id":4948732,"id":"Q4948732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65134df9a487e6d6145032bac5702c761e09f5d5","datavalue":{"value":{"amount":"+0.7870316505432129","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":"Q1071505$E2FFC4C0-EA07-4DF8-8D51-A5B63C8D270A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfe04b69b058b3772fa97654a78be909b5336eaf","datavalue":{"value":{"entity-type":"item","numeric-id":1124331,"id":"Q1124331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16b5f935f171981afa27901096c2427887da7899","datavalue":{"value":{"amount":"+0.7761079668998718","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":"Q1071505$E8D29472-53F9-487F-92A7-6E696B490686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81d22662f0b05050e032c29c2d30510c7c22299e","datavalue":{"value":{"entity-type":"item","numeric-id":3123352,"id":"Q3123352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac844806efe6469398bbf47e0c804f0114dcbcaf","datavalue":{"value":{"amount":"+0.7732570767402649","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":"Q1071505$96486608-1A3D-4669-8849-2AF1EA311D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fdd04af42625621955eb540545348df33eed0f6","datavalue":{"value":{"entity-type":"item","numeric-id":3221420,"id":"Q3221420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8811e8724bb8708202df819129e78d28f5e4015d","datavalue":{"value":{"amount":"+0.7731298804283142","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":"Q1071505$0FC541B4-53D8-4433-B482-7F0F01342775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3046720aac85a1c24cadba625be626e40beca8cc","datavalue":{"value":{"entity-type":"item","numeric-id":4724636,"id":"Q4724636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fa1d234385c73a8af48aae6005b2d7d329ce63a","datavalue":{"value":{"amount":"+0.7729852199554443","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":"Q1071505$397C40AB-6EE6-427D-B780-5E0DA2A14D64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1071505","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1071505"}}}}}