{"entities":{"Q1699287":{"pageid":1710028,"ns":120,"title":"Item:Q1699287","lastrevid":68211276,"modified":"2026-04-12T22:10:02Z","type":"item","id":"Q1699287","labels":{"en":{"language":"en","value":"On Hamiltonian alternating cycles and paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6840483"}},"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":"Q1699287$CE800FA6-A608-4333-AB82-C251D03A1992","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2372e9186fcf61f5a070816d8ab7792a09e03b27","datavalue":{"value":{"text":"On Hamiltonian alternating cycles and paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1699287$C1D5E0DA-2262-4A64-BA88-DC02A4E7DD8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6812730efcf04154e660bb6af867dae7bd17af0","datavalue":{"value":"1386.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$8D88E633-4BC3-48A0-8EE6-A1732AF84878","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7edc8d607796c8219807bdacef3343c990c9ce7","datavalue":{"value":{"entity-type":"item","numeric-id":543791,"id":"Q543791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$A5BBEC77-02D8-4646-8246-649DAD23F139","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"033530fe65204d78ed5b7794895346923088f102","datavalue":{"value":{"entity-type":"item","numeric-id":298634,"id":"Q298634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$2CF0161B-281D-44D4-9650-3903E9D2B0FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e333b473062f409ce440a0394743f717fb6bbf5b","datavalue":{"value":{"entity-type":"item","numeric-id":170492,"id":"Q170492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$B55A7E64-0CB8-47D6-8C17-9464DEA1C7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4cd59bc575d94b62713805c3ad0c404fa5459fb","datavalue":{"value":{"entity-type":"item","numeric-id":828013,"id":"Q828013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$568B6071-5D8C-476B-9E1F-84261AA57A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a34869ff8fac413da0bf3d1185be7c8ae0a75db","datavalue":{"value":{"entity-type":"item","numeric-id":1367694,"id":"Q1367694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$96CE3D69-5F08-42AE-8570-79AB787CF8CB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$82CBC822-13C4-4DAC-934A-1D4AA4491490","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f287bdf783f35305500eed531b35fb7e704778e5","datavalue":{"value":{"time":"+2018-02-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1699287$D81CC0FB-E3C8-44B1-BF2F-4CD9885D67F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"974f0f37114ff5c199e49d31af48dbfcc8873971","datavalue":{"value":"https://arxiv.org/abs/1603.06764","type":"string"},"datatype":"url"},"type":"statement","id":"Q1699287$2D94E780-74D1-4A8B-86F1-BC6EB1BDF594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"4e9943034c57a23fa5e2a2355558c4f2ec9ba802","datavalue":{"value":"http://zaguan.unizar.es/record/78101","type":"string"},"datatype":"url"},"type":"statement","id":"Q1699287$D889DBD5-15DA-4036-956D-FC08E080ED14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d808b95660747f33dac1960bef89c978574d6c17","datavalue":{"value":"Assume we have \\(n\\) red and \\(n\\) blue points in the plane in general position (i.e. no three points are on the same line), \\(n\\geq 2\\). A plane Hamiltonian alternating cycle on this point configuration is a Hamiltonian cycle whose edges are straight-line segments connecting points of different colors with no crossings. Since such cycle does not always exist, instead of being plane a relaxed condition of being 1-plane has been suggested in [the first author et al., ``The alternating path problem revisited'', in: Proceedings of the XV Spanish meeting on computational geometry, Sevilla, June 26--28, 2013. Sevilla: University of Sevilla. 115--118 (2013)], i.e. every edge is allowed to have at most one crossing.  It is shown that a 1-plane Hamiltonian alternating cycle always exists and can be found in \\(O(n^2)\\) time and space. Moreover, when the points are in convex position, every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and such cycle can be found in \\(O(n)\\) time and space.  Further results are obtained for paths between given endpoints on point sets in convex position. It is shown that except certain special configurations, every Hamiltonian alternating path between given endpoints with minimal number of crossings is 1-plane. This allows to find a 1-plane Hamiltonian alternating path between given endpoints with minimum number of crossings in \\(O(n^2)\\) time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699287$6EDA71BE-5726-4061-AA59-8F8343D65959","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9ad4dcbaf6cf92feb249d1615bc4ad1c667e29a1","datavalue":{"value":{"entity-type":"item","numeric-id":313800,"id":"Q313800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$3FF35301-E533-478B-A527-8C488229E231","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$DB2EBEC8-851D-428B-8274-BDC9B189379C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$CC223A8B-EB2E-4848-B5DB-CBBB558BE68F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"af5af707ed729d722feccff88208277cb39cbff7","datavalue":{"value":"52C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$826F10AE-EFD6-4310-9BC8-E3DA86FA62CB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f43ffa4a8bf02b8381fad00dc0e0cbe194471b3","datavalue":{"value":"6840483","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$4C19DF95-90D7-4163-8F77-49BF2F8A1701","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b5d93c14eb1127e147875cf2ddf83d670ca5a59","datavalue":{"value":"bicolored point sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699287$FF33C53F-4C04-4DBA-B833-FB994D780B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a8949c7b07adb9adbc4f9c439a592968f87d4cb","datavalue":{"value":"Hamiltonian alternating cycles and paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699287$279ACA71-8FB3-4351-AC48-8E296736D1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"396300a2f44eb3b4377941b33eb9cdded09e0cc2","datavalue":{"value":"1-plane graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699287$EB335CCA-DCA4-4D84-A665-6C5BB02B94CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92420f550e0b28405b717af146065e97d7343c95","datavalue":{"value":"minimum number of crossings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1699287$26A87593-BBE2-4BFB-B5C6-ACDD65D05DDF","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":"Q1699287$B1B5A205-2592-434F-BBCB-E2728EA21B29","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6ee4b7c51a28402c7c38e5afd86dc1ab30faa50","datavalue":{"value":"W2963240895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$97413B47-07FB-450A-AD97-5FE25CFF3A89","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ec1866ff8c51265e0a52b0469621cef923e15e7","datavalue":{"value":{"entity-type":"item","numeric-id":1296568,"id":"Q1296568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$124333A8-DA81-43E2-8F20-213A74EC1BDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21e8e1f4fd2d0844651838a9e92c3381d1b856f3","datavalue":{"value":{"entity-type":"item","numeric-id":912861,"id":"Q912861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$9C353FC7-ED14-44D1-BDAD-23764A06C559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cceb93cb9b93c334da9441a3e854cfa9129deba","datavalue":{"value":{"entity-type":"item","numeric-id":3156762,"id":"Q3156762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$6A974A52-0016-46E8-9C16-78A2A44B24B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10e61680b4db5e59e2f904ced74b67e15b809d58","datavalue":{"value":{"entity-type":"item","numeric-id":2849801,"id":"Q2849801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$3DED9820-2805-4D85-9124-1EBE36835E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3c204db14874f805f36091d858e53f663e4b599","datavalue":{"value":{"entity-type":"item","numeric-id":5943323,"id":"Q5943323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$38414951-20B2-4668-BEAB-A28049A3D6EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19eec5d5fe787c88328fc2231f3ab8d596dc6086","datavalue":{"value":{"entity-type":"item","numeric-id":1969786,"id":"Q1969786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$0173D905-F1BD-4335-AC2E-076DC6DDEB9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36e4a9599a4233d05f54a9740cbc00a2db96df96","datavalue":{"value":{"entity-type":"item","numeric-id":1196456,"id":"Q1196456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$BDF243D5-FC1C-49F0-8A10-DEC881D7276D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8ecddd2421ddd0dbfb7119ff5230bed9ccf3745","datavalue":{"value":{"entity-type":"item","numeric-id":2847914,"id":"Q2847914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$CF8C00F0-2DA2-4720-8795-97E2F972B6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"167472c3c17eba631e8b872630c9ed2ea84fb046","datavalue":{"value":{"entity-type":"item","numeric-id":5692715,"id":"Q5692715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$63221994-B1F5-402D-8039-4150B08209A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5ba7b970924798810c21530a6def6aa9eed592e","datavalue":{"value":{"entity-type":"item","numeric-id":4682205,"id":"Q4682205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$3FBACEA5-70E3-4390-84DD-2FDBC2EDF902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f99ad9018d17ee697182ca33b9b1ea6fcd12982","datavalue":{"value":{"entity-type":"item","numeric-id":941368,"id":"Q941368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$F73EDE45-D4A5-4462-B445-F0F4C1BD7C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06089c1bffdeebe4c683423018b7412092eb993b","datavalue":{"value":{"entity-type":"item","numeric-id":2901845,"id":"Q2901845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$FA66BE1B-54C0-4228-99D8-9655DA0E9347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f271a9da13360c08f09abec55449a8012199034","datavalue":{"value":{"entity-type":"item","numeric-id":2395454,"id":"Q2395454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$18A27F24-E0F7-4B7F-9CC0-3675EDAC0FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38abf161c81c22020de2d754eded105d734e75b3","datavalue":{"value":{"entity-type":"item","numeric-id":1916126,"id":"Q1916126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1699287$B3BCC8E2-8BAA-4FE3-A543-6C07A1600BD3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9f777bb8cbe7af89d35429a33a5846d4796fed0","datavalue":{"value":"10.1016/J.COMGEO.2017.05.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1699287$2F69D599-27B6-4C83-9A2F-ABC419C4BBD3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b470f17dde265db57d5995b960facd80736f2bd","datavalue":{"value":{"entity-type":"item","numeric-id":4682205,"id":"Q4682205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92a064fbe411b2fc6b0b46b6ff58928e35a754a8","datavalue":{"value":{"amount":"+0.8730103373527527","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":"Q1699287$B6C9B966-FACE-466B-99EF-949A1E4777DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"684eb6d52410677c26ba7d23499c4b77a0f8a29d","datavalue":{"value":{"entity-type":"item","numeric-id":3611851,"id":"Q3611851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"285b41e93e27f129529cad6356b9d4cef34e750f","datavalue":{"value":{"amount":"+0.8523086905479431","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":"Q1699287$6505FE0C-84EA-4E07-AF0B-9D8296E6183B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff8e1c9ec12d2ddbdcd5a7115d075de9a8d02e06","datavalue":{"value":{"entity-type":"item","numeric-id":3111649,"id":"Q3111649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c84e11154a33e5d610e8f599e01d67b55f796e3","datavalue":{"value":{"amount":"+0.830295979976654","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":"Q1699287$557FF9E5-0F87-43CC-817B-D677E38D89EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e4100a3bbfeb2ad037063033aeef533a6f891a2","datavalue":{"value":{"entity-type":"item","numeric-id":340546,"id":"Q340546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099ab3d8dea4df4c551f327c079ccf59ff561c5d","datavalue":{"value":{"amount":"+0.8181840777397156","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":"Q1699287$8A28FD45-4419-4D10-8A5D-84527F8834F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e698e52d4f8f47602ce0a080ba4545dd7fb0118","datavalue":{"value":{"entity-type":"item","numeric-id":2959772,"id":"Q2959772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34ad0dc94fd53c052811a9d49f1711ac42127c64","datavalue":{"value":{"amount":"+0.8097628951072693","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":"Q1699287$BCF6F95C-C3DE-43A3-BB4A-50FA72137A68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On Hamiltonian alternating cycles and paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_Hamiltonian_alternating_cycles_and_paths"}}}}}