BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Abbasnezhad Nazanin (University of Tabriz, Tabriz, Iran), Mehri-Takmeh Javad (University of Tabriz, Tabriz, Iran), Vakili Javad (University of Tabriz, Tabriz, Iran)
Tytuł
The Domination over Time and its Discretisation
Źródło
Operations Research and Decisions, 2020, vol. 30, no. 1, s. 5-24, rys., bibliogr. 24 poz.
Słowa kluczowe
Grafy, Programowanie liniowe, Teoria dualności
Graphs, Linear programming, Theory of duality
Uwagi
summ.
Abstrakt
Domination in graphs is well known and has been an extensively researched branch of graph theory. Since the variation over time is one of the important properties of real-world networks, we study the influence of time on the domination problem. In this paper, we introduce the domination over time problem, including time delay on arcs. Then, an optimal solution to its discretisation is obtained, which is the solution of the original problem. (original abstract)
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka SGH im. Profesora Andrzeja Grodka
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Pełny tekst
Pokaż
Bibliografia
Pokaż
  1. ANDERSON E., A continuous model job shop scheduling, PhD thesis, University of Cambridge, Cambridge 1978.
  2. ANDERSON E., NASH P., Linear programming in infinite-dimensional spaces, Wiley, Chichester, West Sussex, New York 1978.
  3. ANDERSON E.J., NASH P., PEROLD A.F., Some properties of a class of continuous linear programs, SIAM J. Cont. Opt., 1983, 21 (5), 758-765.
  4. BELLMAN R., Dynamic Programming, 1st Ed., Princeton University Press, Princeton 1957.
  5. BERGE C., The Theory of Graphs, Dover Books on Mathematics, Dover 2001.
  6. COCKAYNE E., GOODMAN S., HEDETNIEMI S., A linear algorithm for the domination number of a tree, Inf. Proc. Lett., 1975, 4 (2), 41-44.
  7. COCKAYNE E., HEDETNIEMI S., Towards a theory of domination in graphs, Networks, 1977, 7 (3), 247-261.
  8. FLEISCHER L., SKUTELLA M., Minimum cost flows over time without intermediate storage, [In:] Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), Society of Industrial and Applied Mathematics, ACM, Baltimore 2003, 66-75.
  9. FORD L., FULKERSON D., Constructing maximal dynamic flows from static flows, Oper. Res., 1958, 6 (3), 419-433.
  10. FORD L., FULKERSON D., Flows in Networks, Princeton University Press, 1962.
  11. HASHEMI S.M., NASRABADI E., On solving continuous-time dynamic network flows, J. Global Opt., 2012, 53 (3), 497-524.
  12. HAYNES T., HEDETNIEMI S., SLATER P., Fundamentals of Domination in Graphs, Chapman and Hall, CRC Pure and Applied Mathematics, Taylor and Francis, 1998.
  13. HEDETNIEMI S., HEDETNIEMI S., WIMER T., Linear time resource allocation algorithms for trees, Technical Report URI, INFORMS, 1987, 14.
  14. LUO X., BERTSIMAS D., A new algorithm for state-constrained separated continuous linear programs, SIAM J. Cont. Opt., 1998, 37 (1), 177-210.
  15. PHILPOTT A., CRADDOCK M., An adaptive discretization algorithm for a class of continuous network programs, Networks, 1995, 26 (1), 1-11.
  16. PULLAN M., An algorithm for a class of continuous linear programs, SIAM J. Cont. Opt., 1993, 31 (6), 1558-1577.
  17. PULLAN M., Forms of optimal solutions for separated continuous linear programs, SIAM J. Cont. Opt., 1995, 33 (6), 1952-1977.
  18. PULLAN M., A duality theory for separated continuous linear programs, SIAM J. Cont. Opt., 1996, 34 (3), 931-965.
  19. PULLAN M., Existence and duality theory for separated continuous linear programs, Math. Model. Syst., 1997, 3 (3), 219-245.
  20. PULLAN M., A study of general dynamic network programs with arc time-delays, SIAM J. Opt., 1997, 7 (4), 889-912.
  21. PULLAN M., Convergence of a general class of algorithms for separated continuous linear programs, SIAM J. Opt., 2000, 10 (3), 722-731.
  22. SCHÖBEL A., HAMACHER H., LIEBERS A., WAGNER D., The continuous stop location problem in public transportation networks, Asia-Pacific J. Oper. Res., 2009, 26 (1), 13-30.
  23. SKUTELLA M., An introduction to network flows over time, [In:] W. Cook, L. Lovász, J. Vygen (Eds.), Research Trends in Combinatorial Optimization, Springer, Berlin 2009, 451-482.
  24. WEISS G., A simplex based algorithm to solve separated continuous linear programs, Math. Progr., 2008, 115 (1), 151-198.
Cytowane przez
Pokaż
ISSN
2081-8858
Język
eng
URI / DOI
http://dx.doi.org/10.37190/ord200101
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu