{"entities":{"Q1072571":{"pageid":1083323,"ns":120,"title":"Item:Q1072571","lastrevid":69572193,"modified":"2026-04-13T07:55:26Z","type":"item","id":"Q1072571","labels":{"en":{"language":"en","value":"An efficient Dijkstra-like labeling method for computing shortest odd/even paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3941583"}},"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":"Q1072571$92818055-8736-4F9A-81C8-B4CD85B75BFA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c88c51cbb3b289b29a2df115bde888b19722b1c2","datavalue":{"value":{"text":"An efficient Dijkstra-like labeling method for computing shortest odd/even paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1072571$D354CB04-D811-4FBE-9C02-EF0760B6EF82","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7e1a69ed3f166cce3cc8231f5adfa7ee4eab15e","datavalue":{"value":"0587.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$A71E7A0F-FD86-40D3-83F0-5E1B6B5562AE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4fefac5100dbd65bbcb5c8278517888078075c7","datavalue":{"value":"10.1016/0020-0190(85)90094-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$E4F09D30-9A46-4F18-99CF-F59FEAFF7831","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ab0cdc904b437536dac830900fc48573e948246","datavalue":{"value":{"entity-type":"item","numeric-id":340252,"id":"Q340252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$A1761CDF-DC3F-4204-A148-5E0D720954FE","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":"Q1072571$BC38FF2A-C1F3-44F2-BEFF-6CCAFCF901F5","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":"Q1072571$D74943A0-9EF1-4052-BEA6-E3BC806A0611","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a41519abc92dcbd6dca7a95111a5064fe19d9ef","datavalue":{"value":"The author investigates the problem of determining shortest even (odd resp.) paths in a graph \\(G=(V,E)\\). First, using the connections between matching and augmenting paths in \\(G\\), the theory of shortest augmenting path labeling method is developed. It yields \\(O(| V|^2)\\) procedure for finding the shortest even (odd resp.) path in \\(G\\) joining two specific nodes \\(i\\) and \\(j\\). Secondly, by means of the use of priority queues for storing path labels an \\(O(| E| \\log | V|)\\) labeling method for shortest even paths is described and carefully analyzed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$96B60020-B6C9-4D18-AD0F-FD40DED8142F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$3E3BBD9F-ADE1-4B79-856D-E1A5F6F488C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$E489D4DB-78DB-4DE7-917B-65336FC76448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$1C85C73E-7FDD-4922-B65F-2F2123B01441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$E4AFF66D-142C-49DC-B39C-1D5C25DE404C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"28e9abc2adc3766c8777b31a696b6235209f3fba","datavalue":{"value":"3941583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$2D7D637C-5A55-4701-AA11-4C68F26CC097","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad51c83509d928a081a83d5e68ffdac8db9095ef","datavalue":{"value":"labeling algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$63549A53-D8A6-4D36-A431-568D1A579446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a811bcf660d4ed40688698dd18bb044ec4cf305","datavalue":{"value":"shortest odd path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$C72B5C01-3AC2-4AD4-A474-7C3623A58E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d69d0ee4563fd8442fcad078decdaa73a642a119","datavalue":{"value":"shortest even path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$9E5D3EDC-8034-4664-876B-348353C6FB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$86EF83A3-E771-4287-8E74-ADEB33D1EBDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10073d731ebd75f6f9a6ffd3abe95b2de4890d33","datavalue":{"value":"augmenting paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072571$E29380AF-09E9-493D-B171-BFA82F5063D3","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":"Q1072571$2D0AACCE-68EE-4FF4-96F4-A5E0E9ED2A80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"606ae53c7f314bf300107aa25f2c2737a7c78946","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90094-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1072571$B77463AF-2175-4D2A-B6DE-2D68FF665B33","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"838b912cdee30690449877e204b3110b2a7b6394","datavalue":{"value":"W2054051522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072571$57E0237F-F834-493B-A82D-99CF7EF0643E","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":"Q1072571$C98D2696-60E6-44C5-881C-49B469C663ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c325dd6fba9d2aed5927fab8cf0eb54c2376e6e","datavalue":{"value":{"entity-type":"item","numeric-id":3668867,"id":"Q3668867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$90E24429-2A9E-4E91-BEEC-33C0E1E66991","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e927c80db8e8c562bb886a822cc6867b7d56d1f","datavalue":{"value":{"entity-type":"item","numeric-id":3931440,"id":"Q3931440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$708B8F4C-2613-46DA-B877-9DAAD22504A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f51a2434f0ea0b391aafe6310800f470c1687e44","datavalue":{"value":{"entity-type":"item","numeric-id":798564,"id":"Q798564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$E575E8F9-B198-4167-BFE9-7B05B7B49FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$594E8564-5DAF-4B52-8808-F05BA1B459CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34bc8de7dff9e6ae38acf775674b87311a55dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1169411,"id":"Q1169411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$8230CD8E-C0A7-496B-93AD-99C25471C5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072571$038C4FFF-BE43-4669-80B6-2D568E05823E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91bb1804ba5d58de869bad53d69666b757c5f7ca","datavalue":{"value":{"entity-type":"item","numeric-id":3345793,"id":"Q3345793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc6659481f7faee18d3e0495817b497c9d4ec3b8","datavalue":{"value":{"amount":"+0.7909281849861145","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":"Q1072571$0076AC19-F54B-4C96-8B1E-DA603F7291A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0137a28405dfe6de518cb037b6c897a4c1712127","datavalue":{"value":{"entity-type":"item","numeric-id":3341925,"id":"Q3341925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2a7c78b5ec2fe7dd12878b067a4547b42075214","datavalue":{"value":{"amount":"+0.7758486270904541","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":"Q1072571$4D56ADD8-A276-41A9-AFE1-8AB2D0CE1A4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eafb99db2eeadf6e0a02c281faedfe8749db4a99","datavalue":{"value":{"entity-type":"item","numeric-id":3743140,"id":"Q3743140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b3d93516fe38e3416abe01f17cb2119fea9cdfc","datavalue":{"value":{"amount":"+0.7740433812141418","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":"Q1072571$9464E054-AE79-437F-B81F-8E2F83D0D9DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85d5421527769b3679b76f5cfcd3b4ad8c2f6aeb","datavalue":{"value":{"entity-type":"item","numeric-id":4291478,"id":"Q4291478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"699a9029e0aa24adb264a51e7a41b6c9217767f9","datavalue":{"value":{"amount":"+0.7620372176170349","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":"Q1072571$AFA63FA0-2A98-4532-B967-EE2F503EF6C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9df2825c0ed9717e735a288e8e9fd7b60345ec53","datavalue":{"value":{"entity-type":"item","numeric-id":3710540,"id":"Q3710540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b4b84b409fd0f6997e9edf070888df8813a5139","datavalue":{"value":{"amount":"+0.7602674961090088","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":"Q1072571$ECD022F9-00D6-46D6-B342-297B83FC1F8A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient Dijkstra-like labeling method for computing shortest odd/even paths","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_Dijkstra-like_labeling_method_for_computing_shortest_odd/even_paths"}}}}}