{"entities":{"Q686427":{"pageid":688276,"ns":120,"title":"Item:Q686427","lastrevid":63470886,"modified":"2026-04-11T13:23:14Z","type":"item","id":"Q686427","labels":{"en":{"language":"en","value":"On paths with the shortest average arc length in weighted graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428265"}},"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":"Q686427$58DB5516-3B94-499C-93AE-FAE4A0907DBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d4cdfd2fd0ac46aa12812a8ae2178f0be620f9cb","datavalue":{"value":{"text":"On paths with the shortest average arc length in weighted graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686427$210A69A3-7643-4690-8216-DE326DBFB78A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c767ce3a93957a17f86adff61c1a32c15a9b20b","datavalue":{"value":"0781.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$D723DB66-74E0-4C53-A5C9-0BE3E4E4A604","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8830cd54dc70ecd9a5b66e24f44e6f9096952e61","datavalue":{"value":"10.1016/0166-218X(93)90059-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$65D76BC6-0D09-4587-974B-8D10B9AF30BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bacad6ba42f7180194ad5ec71ec24c687939c81f","datavalue":{"value":{"entity-type":"item","numeric-id":266021,"id":"Q266021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$9A99879A-6E47-4341-A600-8E1C6B8FD41E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ab676d669571e7a6f9865a0b0a60e1db1e54d6e","datavalue":{"value":{"entity-type":"item","numeric-id":686425,"id":"Q686425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$D7FDC5CD-5B53-4312-B8B4-104872BB174F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8bc0f7505205c27dafafb71f7b5a05f307011298","datavalue":{"value":{"entity-type":"item","numeric-id":686426,"id":"Q686426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$F4A7B27D-814A-425B-BE8E-B211AE131451","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":"Q686427$E0D5F7C2-EEC0-44DC-B49A-5945EC3B804A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f76288a30164f14e28f1a275b49eb5d03da81a0a","datavalue":{"value":{"time":"+1993-12-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686427$C67DA3CF-B0D7-4CB3-A275-B99CBDF49FED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e57fe871d8415a0420d3349f6cbe74bf1a3a889e","datavalue":{"value":"The problem of finding the path having the smallest average arc length in an acyclic digraph with a single source and a single sink is considered. This problem arises in VLSI block placement procedures when spreading the building blocks uniformly over the chip area is attempted. A well-known approximation algorithm to find the path with the minimum weight-ratio in a doubly-weighted graph can solve this problem. It combines a combinatorial algorithm with numerical iterations and its time complexity is \\(O(| U|^ 3\\log 1/\\varepsilon)\\), where \\(| U|\\) is the number of vertices and \\(\\varepsilon\\) is the desired accuracy.   The paper presents two new algorithms. The first, called the path length minimization algorithm, is based on the same principles as the algorithm presented by \\textit{R. M. Karp} [Discrete Math. 23, 309-311 (1978; Zbl 0386.05032)] and can also be applied to undirected graphs. It is purely combinatorial and has \\(O(| U|^ 3)\\) time complexity. We show how this algorithm for finding the path with the minimum average arc length can be extended to solve the more general problem of finding the path with the minimum weight-ratio in a doubly-weighted graph for which the secondary arc weights are positive integral or rational numbers. The second algorithm, called the vertex balancing algorithm, approximates the minimum average arc length path in any desired accuracy. It also combines a combinatorial algorithm with numerical iterations. Though having an exponential time complexity, it has been used successfully, achieving rapid convergence in all the practical cases which have been encountered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$59824911-802E-4DE5-8486-66F0C8C10D43","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$CFEB8E71-EB0F-4B40-B7F0-D18647C9D471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$145901D7-2B37-404E-8C4E-09CA4AA100E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$CAD28E1A-E614-4BD7-B1E6-764C982C1471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$CE4A24C7-6DFC-4058-802C-743F077368B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6429f084ae14c816467de72a9a580a5904858636","datavalue":{"value":"428265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686427$CE8C0275-0A2C-42BB-ACFE-653622763D03","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60f4b92bab485ad777738f26bf5dd86283140bf7","datavalue":{"value":"VLSI block placement","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$5C4BA6E0-A582-44B0-8EAB-953DC88753EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4ddfae683b7de787c5ee4b9221a39122f95f38d","datavalue":{"value":"combinatorial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$2793EE91-7910-4D4A-8465-72C280E2E6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85e401ce38aa0327f6296721be2537c81a15902b","datavalue":{"value":"numerical iterations","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$270608DA-6EB8-49E5-9F37-7D547E1BC6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8a8f8b4bbab2aa32e099b625b0ac80542b526a8","datavalue":{"value":"path length minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$64E537A2-77CD-4D5E-B60D-B11AFD08CC1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3eb680a66c6ca448b16fc15fd0456ba4c198a630","datavalue":{"value":"vertex balancing","type":"string"},"datatype":"string"},"type":"statement","id":"Q686427$E944BACC-735D-4372-886E-92885B51ADF5","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":"Q686427$BC36B721-2C75-46C4-ACCF-A910012B1D40","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb763e28b76801553a58db92f777c6c4b53dfe01","datavalue":{"value":{"entity-type":"item","numeric-id":1208448,"id":"Q1208448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$D32C3C90-A167-41D3-9F44-4E3929573AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab4410bd85ba93ca8638378f859367903f5b9ff0","datavalue":{"value":{"entity-type":"item","numeric-id":4083324,"id":"Q4083324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$654D83D6-A5FF-409B-9820-43827058DD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$03997FD8-DFD4-46A9-A246-9A21C9FB8A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f970782cef7606d75b439e57c5964589154083b2","datavalue":{"value":{"entity-type":"item","numeric-id":1249587,"id":"Q1249587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686427$818347C9-A7C8-4C44-BAE4-9361C53B2751","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecc537d91abf3ebbb75b9c3d5c040c62cc782e9d","datavalue":{"value":{"entity-type":"item","numeric-id":6169578,"id":"Q6169578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"297b8f175d4142d903c59079e74ad06a4abd24a8","datavalue":{"value":{"amount":"+0.9143222","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":"Q686427$4A25F71E-7E18-49E3-AAB9-04EAB33A9B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdce4473931c0ad6f8a642856b2d951f09a44b1e","datavalue":{"value":{"entity-type":"item","numeric-id":414929,"id":"Q414929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d0d4f92b46df682f59726265b11e6e29c77e1ec","datavalue":{"value":{"amount":"+0.9052408","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":"Q686427$2EE63207-4E62-4152-8490-2903D13F15E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcf53a88c17e6821e7e5d3fd2d5f1d142ea974ea","datavalue":{"value":{"entity-type":"item","numeric-id":1900895,"id":"Q1900895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0163ce3c8bfec7d5bde90b520a579fe450f67278","datavalue":{"value":{"amount":"+0.90304667","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":"Q686427$E92E7576-159E-4BCC-BB33-217472D88A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaa6acf2731dbe4abc3f33aea4df9d3b6b40a361","datavalue":{"value":{"entity-type":"item","numeric-id":1086251,"id":"Q1086251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea0f7b6416397d7dcb4ff547548b43293a01a13f","datavalue":{"value":{"amount":"+0.8938589","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":"Q686427$F82F34E8-93A7-48DD-ADC7-1E68EF6C75E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"722058e5d336986d53ece35042aa7287e24f9956","datavalue":{"value":{"entity-type":"item","numeric-id":4896279,"id":"Q4896279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8102ad1ea7b9f4f1b9cff0a1ff63a51245a7fb15","datavalue":{"value":{"amount":"+0.89306414","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":"Q686427$89185293-8AF9-44E3-A047-0BDB5BDF5C27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1b9ffabeeb7e2a2a224e42a3b041b10eb238290","datavalue":{"value":{"entity-type":"item","numeric-id":3699721,"id":"Q3699721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15538b3029acf88ce53accc984c7db32335edba5","datavalue":{"value":{"amount":"+0.8924518","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":"Q686427$2E5EEE2D-81C3-4172-8E7F-8B038108A4DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fc3f57dd6e4d10e9202e7ccfb94e975f57b00f9","datavalue":{"value":{"entity-type":"item","numeric-id":2225067,"id":"Q2225067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eac39e4921ae2bf71ed0c92aa08600fab030606","datavalue":{"value":{"amount":"+0.89040387","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":"Q686427$AB22EAC7-B40D-4DD4-A30F-C0671DC49884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c51fd30ec8dd9ed0b30a3ba518d3b4d7a7a08a7","datavalue":{"value":{"entity-type":"item","numeric-id":4005305,"id":"Q4005305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"698c2d4577d68a3419808d64b69b40a47a9bc72d","datavalue":{"value":{"amount":"+0.88849723","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":"Q686427$3F9085B6-6B34-4764-ADF7-33E669375DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c60aab4075bafd81a9dc28f7956e5ecea06b87e","datavalue":{"value":{"entity-type":"item","numeric-id":2230798,"id":"Q2230798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a522640ef3e230fedd48ddd1ef0a56ca1bbd1d49","datavalue":{"value":{"amount":"+0.8877203","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":"Q686427$8A5E13E7-AF6D-407B-B9A7-FA1167DCBCBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68d50230892e08491d88e4928669b53fd0b602f2","datavalue":{"value":{"entity-type":"item","numeric-id":6085709,"id":"Q6085709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04a3821085030bb9e097a8d4a2b6fbb86306c2f3","datavalue":{"value":{"amount":"+0.8869674","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":"Q686427$CC377C82-775D-476F-BC64-880F885C9A45","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On paths with the shortest average arc length in weighted graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_paths_with_the_shortest_average_arc_length_in_weighted_graphs"}}}}}