The Domination over Time and its Discretisation

• Autorzy: Nazanin Abbasnezhad , Javad Mehri-Takmeh , Javad Vakili
• 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. (original abstract)

Słowa kluczowe

EN

Graphs; Linear programming; Theory of duality

PL

Grafy; Programowanie liniowe; Teoria dualności

• Czasopismo: Operations Research and Decisions
• Rocznik: 2020
• Tom: 30
• Numer: nr 1
• Strony: 5--24

Twórcy

autor

Nazanin Abbasnezhad

• University of Tabriz, Tabriz, Iran

autor

Javad Mehri-Takmeh

• University of Tabriz, Tabriz, Iran

autor

Javad Vakili

• University of Tabriz, 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.

Identyfikatory

DOI

10.37190/ord200101