The domination over time and its discretisation

• Autorzy: Abbasnezhad Nazanin , Mehri-Takmeh Javad , Vakili Javad

Identyfikatory

DOI

10.37190/ord200101

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

domination over time; continuous linear programming; duality; discretisation

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2020
• Tom: Vol. 30, No. 1
• Strony: 5--24
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Abbasnezhad Nazanin

• Department of Applied Mathematics, School of Mathematics Science, University of Tabriz, 29 Bahman Blvd., Tabriz, Iran

autor

Mehri-Takmeh Javad

• Department of Applied Mathematics, School of Mathematics Science, University of Tabriz, 29 Bahman Blvd., Tabriz, Iran

autor

Vakili Javad

• Department of Applied Mathematics, School of Mathematics Science, University of Tabriz, 29 Bahman Blvd., Tabriz, Iran

Bibliografia

• [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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).