{"entities":{"Q1842658":{"pageid":1853400,"ns":120,"title":"Item:Q1842658","lastrevid":69096666,"modified":"2026-04-13T04:45:48Z","type":"item","id":"Q1842658","labels":{"en":{"language":"en","value":"Alternating paths in edge-colored complete graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 750907"}},"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":"Q1842658$7DF8E846-0346-42B3-BC18-F2264AE0F455","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e81bed42f9efb28c0b33c3c74e3b2375b95c2ff3","datavalue":{"value":{"text":"Alternating paths in edge-colored complete graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842658$9268E379-3AFB-45D2-82AB-E1FDC5464C89","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01b46b340abb8cb7659fa0364b73b5059bda9f07","datavalue":{"value":"0819.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$104E475E-0B23-4306-A9CC-16184676167E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4eeb3ba5786d1c4c50b353c8c7baf7ce6967d13","datavalue":{"value":"10.1016/0166-218X(94)00091-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$145EB481-E58E-4EC7-A120-BE111D99A6E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"09cdf532be71805c5a55207577a015b56c8e9f13","datavalue":{"value":{"entity-type":"item","numeric-id":442365,"id":"Q442365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$23CD7D7C-643D-4B7B-9F27-25FDB920724F","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":"Q1842658$F2AF8F8A-C63E-4198-A7F0-B5F702F4F3AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7004dab7195f76b52ad610efbf3c1d77a19afe78","datavalue":{"value":{"time":"+1995-05-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842658$3F241D7B-62D3-4099-AEF4-04EDD5F59A14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aa1f71798e939236886085c88da8c649e05b1cbc","datavalue":{"value":"An alternating path in an edge-colored graph is a path in which every two adjacent edges have different colors. In this paper, an \\(O(n^{2.5})\\) algorithm is given for finding the maximum number of internally vertex- disjoint alternating paths between a specified pair of vertices in an edge-colored complete graph. Related problems are studied in which further restrictions on the paths and on the edge-colorings are imposed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$6281461F-BBF1-4402-A184-40DA22BB77E6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8ba0869bc4942831c8669ed75022f72a56f93072","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$00BB56A7-DD6A-45DE-93AA-A53085DD372D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$7DCF0BD6-5423-4882-A712-453418F625AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$D8839416-9CDE-4187-8102-B20C69C64196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$C19EF2B8-9B8F-4807-BA32-FEA55FBE6EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$AA100EAF-50BB-47C2-BDF9-55CE60EBCACE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10940ebe56fd1f7208d9b65e9883b6e809bd34dd","datavalue":{"value":"750907","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842658$62D0A6AC-9DB3-4317-BCE4-8DB4F58A7469","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$8F749696-37F3-4C2E-B3F1-B6626B539B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96628524c5fc80ddd87317af34daeb09586a38ba","datavalue":{"value":"alternating path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$4D706DCF-30EA-4695-BD2D-D456E774CBA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16b0b14615050195933c50b91405fa4d1652e9dc","datavalue":{"value":"edge-colored graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$540644BA-8046-4989-AFEB-B2EB6CB81DC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$D91C9FDB-E972-4FEE-B78D-5CB5F6FC6EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f2bd7369831d9e54b4e511b9d71ba97d1e383ac","datavalue":{"value":"complete graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$6429BE90-A6FD-4976-89F4-9E5DF4B0225A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"908662a7a1ef8bdd83cf0e3c7fe5f8e5b2240d6f","datavalue":{"value":"edge-colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842658$C6794909-BF9B-4F07-811B-656D3D6A2243","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":"Q1842658$3A4EA1A6-DAC8-4D92-BAE2-1FA985A07EFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b59b9a95c5ede48fa66f5efb685b30e863d99e05","datavalue":{"value":{"entity-type":"item","numeric-id":3948568,"id":"Q3948568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$FF6B52AD-EC86-474D-9551-CDB25570CA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b86e72a26e33825519346307d94ebc6c9adfe16e","datavalue":{"value":{"entity-type":"item","numeric-id":751274,"id":"Q751274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$A8B65B3F-2D39-4024-AE64-CBF332A666A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c61ab52ec8455b4e1daf7ef8acb2d85d5644bd52","datavalue":{"value":{"entity-type":"item","numeric-id":5545296,"id":"Q5545296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$35D6C245-7618-4BEA-9D14-597407C29D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9a7eba2794d9b74ebf26ef5b1b6447c802547e5","datavalue":{"value":{"entity-type":"item","numeric-id":5689636,"id":"Q5689636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$7239AB12-D843-4116-99E8-D1712C19AB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc3b77283ff43cd643d5b39c9b4770d340884522","datavalue":{"value":{"entity-type":"item","numeric-id":4320687,"id":"Q4320687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$FB1FC8DE-B168-4159-9A92-D17EB2959938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae2c38374506493b1f59210638c268751587752b","datavalue":{"value":{"entity-type":"item","numeric-id":1869211,"id":"Q1869211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$3C8FC8C8-DB67-433F-BF99-3A9A53A4F65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1106603c0cc29b2d22c91be53851a0120fb22c6","datavalue":{"value":{"entity-type":"item","numeric-id":1225065,"id":"Q1225065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$5A59EBD8-A4FF-4CFE-9B4A-B9131024A627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c6860e82de1ce9918bd6feeb811c980cb5d663","datavalue":{"value":{"entity-type":"item","numeric-id":1845739,"id":"Q1845739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$5B041E38-4F3E-4A45-B40B-D6E65182E109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$09C332EB-67C1-4694-9AC3-415F18F3ACBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$96CE9B2C-2AC3-488C-BD63-4E876DE5E05E","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":"Q1842658$D3286B70-9BA3-4FB7-B944-FF3D2D4B0B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de4a75fb6428860e9bdeb8df08502e8c30d9e548","datavalue":{"value":{"entity-type":"item","numeric-id":1331890,"id":"Q1331890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$0BACA0C9-D012-42FD-A8D8-389FC5CA51EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$3ECE038A-8799-4581-9DDF-43DF8870F09B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842658$E9A19B3A-284B-4A51-907E-9093C75334ED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acfcdb9dd1982a72dd2cc696cb8f1526d4c52753","datavalue":{"value":{"entity-type":"item","numeric-id":5689636,"id":"Q5689636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7308db568209a653218d363a9499cdac4ad8293","datavalue":{"value":{"amount":"+0.8545106053352356","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":"Q1842658$0A55436D-B177-483F-A42D-A44266383400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8fbff099c3c0f3dc54d2340fc2c7b10d162e06f","datavalue":{"value":{"entity-type":"item","numeric-id":1356728,"id":"Q1356728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73243757e30f5054fa405b206388c0c61801a4b2","datavalue":{"value":{"amount":"+0.8528388142585754","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":"Q1842658$A78F2367-2110-4D04-97CD-CC0033D5A485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"838de678e5539c184540620d919badadaf35fa92","datavalue":{"value":{"entity-type":"item","numeric-id":2014212,"id":"Q2014212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18097dc742b7b9e032c08cfbdd62f83cde1f3b5c","datavalue":{"value":{"amount":"+0.8374806642532349","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":"Q1842658$2569134E-5F1F-4D2F-A578-8471346DBAA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f213077e61558b67c28ba56319c447a11b376c0","datavalue":{"value":{"entity-type":"item","numeric-id":4320687,"id":"Q4320687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb2de991b3326fae80dfe425f30e0e955368ea89","datavalue":{"value":{"amount":"+0.833254873752594","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":"Q1842658$447AF568-6D38-410B-BE25-9D0E87B39AE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating paths in edge-colored complete graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_paths_in_edge-colored_complete_graphs"}}}}}