PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

The domination over time and its discretisation

Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
5--24
Opis fizyczny
Bibliogr. 24 poz., rys.
Twórcy
  • Department of Applied Mathematics, School of Mathematics Science, University of Tabriz, 29 Bahman Blvd., Tabriz, Iran
  • Department of Applied Mathematics, School of Mathematics Science, University of Tabriz, 29 Bahman Blvd., Tabriz, Iran
autor
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5e7e0ad3-155f-497e-8c3f-3f3d822b7d5e
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.