{"entities":{"Q800837":{"pageid":802685,"ns":120,"title":"Item:Q800837","lastrevid":42699708,"modified":"2025-07-08T14:52:20Z","type":"item","id":"Q800837","labels":{"en":{"language":"en","value":"On the windy postman problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3878708"}},"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":"Q800837$BAD536FE-BB32-4399-BED7-F08D2EEDDAA0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe99e95137d0879dbc286c6f3b2c27dd9458a64e","datavalue":{"value":{"text":"On the windy postman problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800837$EEEDE31A-7590-4C07-AF60-702D09262B67","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1690c6592ed150262cae838e80c276b8fd70d616","datavalue":{"value":"0551.90092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$6BA616C6-FD79-4DF9-A83A-9A2DA8CB650D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82c704292c8ab6aa83c4672538457093012ae872","datavalue":{"value":"10.1016/0166-218X(84)90089-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$A3B16EC9-9E68-430E-8F78-731E929656E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e75f57d633aad96bfc46a4633619478c83608c95","datavalue":{"value":{"entity-type":"item","numeric-id":787995,"id":"Q787995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800837$8885E6A9-7197-4FDC-A4E0-30D8246DD341","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":"Q800837$95B8DFEE-F92C-4034-8789-F72D68D119A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q800837$0BB56483-7455-4F50-BDC2-62C9B12B146C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"99836b372d8c14672cf858016aa7375b21526da0","datavalue":{"value":"The windy postman problem (WPP) is: find a shortest postman route in a connected undirected graph G(V,E), such that for every edge (x,y) the distance from x to y can be different from the distance from y to x. The author proves that WPP is NP-hard. Further, the WPP is restated as follows: let \\(G_ 1(V,A)\\) be a symmetric directed graph, where for every edge \\(e=(x,y)\\) in E there are two arcs \\(a'=(x,y)\\) and \\(a''=(y,x)\\) in A with a non-negative length \\(\\ell (a')\\) and \\(\\ell(a'')\\). The problem is to find a shortest directed closed path p in \\(G_ 1\\), such that for every \\(e\\in E\\) at least a' or a'' belong to p. A polynomial bounded algorithm is given for solving WPP if the following condition Q is fulfilled: for every cycle C in G the corresponding cycles C' and C'' obtained from C with the two possible directions have the same length, i.e. \\(\\ell(C')=\\ell(C'').\\)    Theorem 3 makes the procedure proving condition Q simpler. The author considers also the case when condition Q is ''nearly'' satisfied. G satisfies condition \\(Q_ 1\\), if for any cycle C in G and any edge \\(e\\in C\\), \\(| \\ell(C')-\\ell(C'')| <\\ell(a')+\\ell(a'').\\)    Theorem 5. If there exists a real number \\(\\epsilon\\geq 0\\) and a spanning tree T of G, such that (a) for every fundamental cycle \\(C_ i\\), \\(| \\ell (C'_ i)-\\ell (C''_ i)| \\leq \\epsilon /s\\) (s is the cyclomatic number of G), (b) for every edge e of G, \\(\\ell(a')+\\ell(a'')>\\epsilon\\), then condition \\(Q_ 1\\) is satisfied.    If G satisfies conditions (a) and (b) of Theorem 5, a polynomial bounded algorithm \\((\\bar A)\\) is given for solving WPP approximately.    Theorem 6. Let \\(p_ 1\\) be the shortest postman route of the WPP on G, and p be the postman route obtained by algorithm \\(\\bar A.\\) Then \\(| \\ell (p_ 1)\\)-\\(\\ell (p)| <s\\epsilon\\) (s and \\(\\epsilon\\) are meant as in Theorem 5).","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$B6B57544-E0C6-4A9E-8586-5B9EC76FE7B5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$98B2A395-E2CB-47C7-BE24-437C67F8D511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$A7E9C51F-300C-445C-8C77-3A4E752F9E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$D2FB5750-F2F4-42E2-97F2-93241B8CC2D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fa6c7d6361c29a7bebaeefbdf5345c9a77f9b0c7","datavalue":{"value":"3878708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$F4AFFD17-8AC0-418B-B495-CC6C6D0CA075","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3e4a080961e9d997a8b36f055c2ccdc6405d2fb","datavalue":{"value":"chinese postman","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$486D4935-FA00-4FB9-BC84-9744A663155F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$C548CD89-F83C-43D2-B167-70BED0DA8236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0757bafa7a9039e28e7ede135ec008acd1731a99","datavalue":{"value":"windy postman problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$ABBAB888-E96D-4FA6-B75D-1C7D83154F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d86c1fd3ac13577921195e75692323c2703bfc4a","datavalue":{"value":"connected undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$8C1901E1-4BC1-4558-8408-81CEFFB0E16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16c83a88426940392491ee858f450a3f943e96f6","datavalue":{"value":"polynomial bounded algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q800837$C51A1D2B-B81B-463F-A62A-519B96F2ABFC","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"44610543562d7290ca32f748f0c98a6cae1f7093","datavalue":{"value":"Q55968052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$347C6620-5802-4C70-A28E-51511ABD7430","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":"Q800837$0AC57D33-23EB-4C5B-A307-83E99C28CB0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"95d6f3d072da4061fa9dce9b51cd73214e1c3889","datavalue":{"value":{"entity-type":"item","numeric-id":3858019,"id":"Q3858019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800837$E72E85F0-6611-4A33-A76D-E73330B92D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5f53b74fbc5be34744e0395c6cddee6347ba8b6","datavalue":{"value":{"entity-type":"item","numeric-id":4121714,"id":"Q4121714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800837$7E813F7C-A09A-4BCF-9773-B2DD43D075E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800837$EB56667C-0B8B-43AF-B708-16FD9A2C294C","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"3262add0f4829f8cfa422e03cd36d5b18990c649","datavalue":{"value":"journals/dam/Guan84","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800837$773AF659-3E8B-48B4-84AA-39E5DC459A00","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca4e0617bc9d77de48f408c4159c1f2c121c50ad","datavalue":{"value":{"entity-type":"item","numeric-id":2429464,"id":"Q2429464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e2a5450185460d7db7547f1546e56dcde61eb8e","datavalue":{"value":{"amount":"+0.9203143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$88CFB12A-B4EC-4206-B830-66446EA13641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5de8f97d6a59414e5ea9b76f110b5417c6f8f2d","datavalue":{"value":{"entity-type":"item","numeric-id":1332802,"id":"Q1332802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfb4515ee6b2a3723ec45047d778e7715f2790fe","datavalue":{"value":{"amount":"+0.91539717","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$A38BB44B-E583-47A6-818A-50F429A21CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9692f98005f7649e776da918d3e084be859eb8db","datavalue":{"value":{"entity-type":"item","numeric-id":1119487,"id":"Q1119487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b82abafc726eae4c0d645eecca5af7b1b5668624","datavalue":{"value":{"amount":"+0.8708066","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$B21C99F7-E954-4E0C-B15A-80D3CB95D20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c396783b0c5aa1d92c8805d78b81253952555bb","datavalue":{"value":{"entity-type":"item","numeric-id":1751757,"id":"Q1751757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64f3c6b48efa90bb05218a48bb5e01b217661fd4","datavalue":{"value":{"amount":"+0.8699862","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$A7737FF6-BE33-4B93-A26A-747D2647AB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33401625ac860adba530c71e212c4eebf7572c07","datavalue":{"value":{"entity-type":"item","numeric-id":1198736,"id":"Q1198736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbfd837710dd18f8ffaeb373f859c815399ef4e0","datavalue":{"value":{"amount":"+0.85654086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$E427E066-991B-451B-AC78-757119D82669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0533ca4a91e91092a29342f3e8f5cd4d115a6363","datavalue":{"value":{"entity-type":"item","numeric-id":3576681,"id":"Q3576681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c27c92c34bfb3d3fd9c3419de55ca0640c57c8f0","datavalue":{"value":{"amount":"+0.856063","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$5B3FACB2-E0D5-4220-8341-07C672C8D2D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1424c4d5519c0329cba949ad8b2f6e94a6f0f048","datavalue":{"value":{"entity-type":"item","numeric-id":340318,"id":"Q340318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c191069ede6b3ac46a7550b6ddb6c7a2328c76","datavalue":{"value":{"amount":"+0.8369793","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$057AB808-73FA-4B5F-A715-76019E69DCFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"982d4505baff0bcfb2dd74bf8c99b21e87a17798","datavalue":{"value":{"entity-type":"item","numeric-id":852946,"id":"Q852946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28700f66b202a704e2e926ddabec63333adab7d2","datavalue":{"value":{"amount":"+0.82829314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$29AB441C-2DF5-43E9-B8E8-712C42185F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe97b0b5130f8608b04498b2e14631b2ca257858","datavalue":{"value":{"entity-type":"item","numeric-id":2387296,"id":"Q2387296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94e0426add767a27b46f21c72f4b69ccc8ea3a59","datavalue":{"value":{"amount":"+0.8250703","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800837$16596445-134D-452F-A166-15B53774C64E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:800837","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:800837"}}}}}