Skip to main content
Top
Published in: Telecommunication Systems 4/2016

11-03-2016

An \(O(mn \log U)\) time algorithm for estimating the maximum cost of adjusting an infeasible network

Author: Mehdi Ghiyasvand

Published in: Telecommunication Systems | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper presents an \(O(mn \log U)\) time algorithm to solve the feasibility problem, where nm and U are the number of nodes, arcs, and the value of maximum upper bound, respectively. The merit of this paper in comparison with maximum flow algorithms, is that it presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network. Our algorithm improves upon the previous \(O(mn \log (nU))\)-time method due to Ghiyasvand (Appl Math Modell 35:5276–5285, 2011). Also, the algorithm computes a feasible flow if the given network is feasible, but the method of Ghiyasvand (Appl Math Modell 35:5276–5285, 2011) does not compute a feasible flow if it is feasible.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice-Hall. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice-Hall.
2.
go back to reference Busch, C., Kannan, R., & Vasilakos, A. V. (2012). Approximating ongestion + ilation in networks via quality of routing games. IEEE Transactions on Computers, 61, 1270–1283.CrossRef Busch, C., Kannan, R., & Vasilakos, A. V. (2012). Approximating ongestion + ilation in networks via quality of routing games. IEEE Transactions on Computers, 61, 1270–1283.CrossRef
3.
go back to reference Cheng, H., Xiongb, N., Vasilakos, A. V., Yangd, L. T., Chena, G., & Zhuanga, X. (2012). Nodes organization for channel assignment withtopology preservation in multi-radio wireless mesh networks. Ad Hoc Networks, 10(5), 760–773.CrossRef Cheng, H., Xiongb, N., Vasilakos, A. V., Yangd, L. T., Chena, G., & Zhuanga, X. (2012). Nodes organization for channel assignment withtopology preservation in multi-radio wireless mesh networks. Ad Hoc Networks, 10(5), 760–773.CrossRef
4.
go back to reference Chilamkurti, N., Zeadally, S., Vasilakos, A., & Sharma, V. (2009). Cross-layer support for energy efficient routing in wireless sensor networks. Journal of Sensors, 1, 1–9. Chilamkurti, N., Zeadally, S., Vasilakos, A., & Sharma, V. (2009). Cross-layer support for energy efficient routing in wireless sensor networks. Journal of Sensors, 1, 1–9.
5.
go back to reference Salehi Fathabadi, H., & Ghiyasvand, M. (2007). A new algorithm for solving the feasibility problem of a network flow. Applied Mathematics and Computation, 192(2), 429–438.CrossRef Salehi Fathabadi, H., & Ghiyasvand, M. (2007). A new algorithm for solving the feasibility problem of a network flow. Applied Mathematics and Computation, 192(2), 429–438.CrossRef
6.
go back to reference Ghiyasvand, M. (2011). An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem. Applied Mathematical Modelling, 35, 5276–5285.CrossRef Ghiyasvand, M. (2011). An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem. Applied Mathematical Modelling, 35, 5276–5285.CrossRef
7.
go back to reference Ghiyasvand, M. (2016). Adjusting an infeasible network by minimizing the sum of the violation costs. Scientia Iranica (accepted). Ghiyasvand, M. (2016). Adjusting an infeasible network by minimizing the sum of the violation costs. Scientia Iranica (accepted).
8.
go back to reference Ghiyasvand, M. (2006). A new approach for computing a most positive cut using the minimum flow algorithms. Applied Mathematics and Computation, 176(1), 27–36.CrossRef Ghiyasvand, M. (2006). A new approach for computing a most positive cut using the minimum flow algorithms. Applied Mathematics and Computation, 176(1), 27–36.CrossRef
9.
go back to reference Li, M., Li, Z., & Vasilakos, A. V. (2013). A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues. Proceedings of the IEEE, 101(12), 2538–2557.CrossRef Li, M., Li, Z., & Vasilakos, A. V. (2013). A survey on topology control in wireless sensor networks: taxonomy, comparative study, and open issues. Proceedings of the IEEE, 101(12), 2538–2557.CrossRef
10.
go back to reference Li, P., Guo, S., Yu, S., & Vasilakos, A. V. (2012). An opportunistic feeding and routing protocol for reliable multicast with pipelined network coding. In Proceedings of the IEEE INFOCOM 2012 (pp. 100–108). Li, P., Guo, S., Yu, S., & Vasilakos, A. V. (2012). An opportunistic feeding and routing protocol for reliable multicast with pipelined network coding. In Proceedings of the IEEE INFOCOM 2012 (pp. 100–108).
11.
go back to reference Hoffman, A. J. (1960). Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics (Vol. X, pp. 113–127). Hoffman, A. J. (1960). Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics (Vol. X, pp. 113–127).
12.
go back to reference McCormick, S. T. (1997). How to compute least infeasible flows. Mathematical Programming, 78, 179–194. McCormick, S. T. (1997). How to compute least infeasible flows. Mathematical Programming, 78, 179–194.
13.
go back to reference Meng, T., Wu, F., Yang, Z., Chen, G., & Vasilakos, A. V. (2016). Spatial reusability-aware routing in multi-hop wireless networks. IEEE Transactions on Computers, 65, 244–255.CrossRef Meng, T., Wu, F., Yang, Z., Chen, G., & Vasilakos, A. V. (2016). Spatial reusability-aware routing in multi-hop wireless networks. IEEE Transactions on Computers, 65, 244–255.CrossRef
14.
go back to reference Orlin, J. B. (2013). Max Flows in O(nm) time, or better. Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 765–774). New York. Orlin, J. B. (2013). Max Flows in O(nm) time, or better. Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 765–774). New York.
15.
go back to reference Quan, W., Xu, C., Vasilakos, A. V., Guan, J., Zhang, H., & Grieco, L. A. (2014). Tree-bitmap and bloom-filter for a scalable and efficient name lookup in content-centric networking. Networking Conference, 2014 IFIP (pp. 1–9). IEEE. Quan, W., Xu, C., Vasilakos, A. V., Guan, J., Zhang, H., & Grieco, L. A. (2014). Tree-bitmap and bloom-filter for a scalable and efficient name lookup in content-centric networking. Networking Conference, 2014 IFIP (pp. 1–9). IEEE.
16.
go back to reference Spyropoulos, T., Rais, R. N. B., Turletti, T., Obraczka, K., & Vasilakos, A. (2010). Routing for disruption tolerant networks: Taxonomy and design. Wireless Networks, 16(8), 2349–2370.CrossRef Spyropoulos, T., Rais, R. N. B., Turletti, T., Obraczka, K., & Vasilakos, A. (2010). Routing for disruption tolerant networks: Taxonomy and design. Wireless Networks, 16(8), 2349–2370.CrossRef
17.
go back to reference Vasilakos, A. V., Saltouros, M. P., Atlassis, A. F., & Pedrycz, W. (2003). Optimizing qos routing in hierarchical ATM networks using computational intelligence techniques. IEEE Transactions on Systems, Man, and Cybernetics, 33(3), 297–312.CrossRef Vasilakos, A. V., Saltouros, M. P., Atlassis, A. F., & Pedrycz, W. (2003). Optimizing qos routing in hierarchical ATM networks using computational intelligence techniques. IEEE Transactions on Systems, Man, and Cybernetics, 33(3), 297–312.CrossRef
18.
go back to reference Vasilakos, A. V., Zhang, Y., & Spyropoulos, T. (2012). Delay tolerant networks: Protocols and applications. Boca Rotan: CRC press. Vasilakos, A. V., Zhang, Y., & Spyropoulos, T. (2012). Delay tolerant networks: Protocols and applications. Boca Rotan: CRC press.
19.
go back to reference Wang, X., Vasilakos, A. V., Chen, M., Liu, Y., & Kwon, T. T. (2012). A survey of green mobile networks: Opportunities and challenges. MONET, 17(1), 4–20. Wang, X., Vasilakos, A. V., Chen, M., Liu, Y., & Kwon, T. T. (2012). A survey of green mobile networks: Opportunities and challenges. MONET, 17(1), 4–20.
20.
go back to reference Xiang, L., Luo, J., & Vasilakos, A. V. (2011). Compressed data aggregation for energy efficient wireless sensor networks. In Global Telecommunications Conference (GLOBECOM 2011) (pp. 1–5). IEEE. Xiang, L., Luo, J., & Vasilakos, A. V. (2011). Compressed data aggregation for energy efficient wireless sensor networks. In Global Telecommunications Conference (GLOBECOM 2011) (pp. 1–5). IEEE.
21.
go back to reference Yao, Y., Cao, Q., & Vasilakos, A. V. (2013). An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for wireless sensor networks. In IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems (pp. 182–190). IEEE. Yao, Y., Cao, Q., & Vasilakos, A. V. (2013). An energy-efficient, delay-aware, and lifetime-balancing data collection protocol for wireless sensor networks. In IEEE 10th International Conference on Mobile Ad-Hoc and Sensor Systems (pp. 182–190). IEEE.
22.
go back to reference Yen, Y. S., Chao, H. C., Chang, R. S., & Vasilakos, A. V. (2011). Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs. Mathematical and Computer Modelling, 53, 2238–2250. Yen, Y. S., Chao, H. C., Chang, R. S., & Vasilakos, A. V. (2011). Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs. Mathematical and Computer Modelling, 53, 2238–2250.
23.
go back to reference Youssef, M., Ibrahim, M., Abdelatif, M., Che, L., & Vasilakos, A. V. (2014). Routing metrics of cognitive radio networks: A survey. IEEE Communications Surveys and Tutorials, 16(1), 92–109.CrossRef Youssef, M., Ibrahim, M., Abdelatif, M., Che, L., & Vasilakos, A. V. (2014). Routing metrics of cognitive radio networks: A survey. IEEE Communications Surveys and Tutorials, 16(1), 92–109.CrossRef
24.
go back to reference Zeng, Y., Xiang, K., Li, D., & Vasilakos, A. V. (2013). Directional routing and scheduling for green vehicular delay tolerant networks. Wireless Networks, 19(2), 161–173.CrossRef Zeng, Y., Xiang, K., Li, D., & Vasilakos, A. V. (2013). Directional routing and scheduling for green vehicular delay tolerant networks. Wireless Networks, 19(2), 161–173.CrossRef
25.
go back to reference Zhang, B., Wang, Y., Vasilakos, A. V., & Ma, J. (2013). Mobile social networking: Reconnect virtual community with physical space. Telecommunication Systems, 54(1), 91–110.CrossRef Zhang, B., Wang, Y., Vasilakos, A. V., & Ma, J. (2013). Mobile social networking: Reconnect virtual community with physical space. Telecommunication Systems, 54(1), 91–110.CrossRef
26.
go back to reference Zhou, L., Chao, H. C., & Vasilakos, A. V. (2011). Joint forensics-scheduling strategy for delay-sensitive multimedia applications over heterogeneous networks. IEEE Journal on Selected Areas in Communications, 29(7), 1358–1367.CrossRef Zhou, L., Chao, H. C., & Vasilakos, A. V. (2011). Joint forensics-scheduling strategy for delay-sensitive multimedia applications over heterogeneous networks. IEEE Journal on Selected Areas in Communications, 29(7), 1358–1367.CrossRef
Metadata
Title
An time algorithm for estimating the maximum cost of adjusting an infeasible network
Author
Mehdi Ghiyasvand
Publication date
11-03-2016
Publisher
Springer US
Published in
Telecommunication Systems / Issue 4/2016
Print ISSN: 1018-4864
Electronic ISSN: 1572-9451
DOI
https://doi.org/10.1007/s11235-016-0151-9

Other articles of this Issue 4/2016

Telecommunication Systems 4/2016 Go to the issue