Skip to main content
SpringerLink
Log in

Static and dynamic source locations in undirected networks

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented; for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. The running time for this step can be reduced to \(\mathcal {O}(n\log n)\) in the context of our algorithm as follows: for each vertex \(v\in V\) we build a binary max-ordered heap \(H_v\) containing the other vertices with key values \(\text {Val}(v_j,v)\). Since a heap can be built in linear time, this needs overall time \(\mathcal {O}(n^2)\) once. Then, in order to check whether \(V{\setminus } \{v_j\}\) is a single cover, we delete \(v_j\) from each of the heaps \(H_v\) (\(v\in V{\setminus } S)\) and then check whether the maximum value in each of these heaps still at least \(d_v\). This needs \(\mathcal {O}(n)\) heap operations, each of which can be accomplished in time \(\mathcal {O}(\log n)\). If \(S{\setminus }\{v_j\}\) is not a cover, we need to re-insert \(v_j\) into the heaps, which again needs time \(\mathcal {O}(n\log n)\).

References

  • Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, Upper Saddle River

    Google Scholar 

  • Andreev K, Garrod C, Maggs B, Meyerson M (2004) Simultaneous source location. In: Jansen K, Khanna S, Rolim JDP, Ron D (eds) APPROX/RANDOM 2004—approximation, randomization, and combinatorial optimization: algorithms and techniques, Proceedings of the 7th international workshop on approximation algorithms for combinatorial optimization problems and the 8th international workshop on randomization and computation, Cambridge, USA, August 22–24, 2004, Lecture notes in computer science, vol 3122. Springer, Berlin, pp 13–26

  • Arata K, Iwata S, Makino K, Fujishige S (2002) Locating sources to meet flow demands in undirected networks. J Algorithms 42:54–68

    Article  Google Scholar 

  • Arata K, Iwata S, Makino K, Fujishige S (2000) Locating sources to meet flow demands in undirected networks. In: Halldórsson MM (ed) SWAT 2000—algorithm theory: proceedings of the 7th scandinavian workshop on algorithm theory, Bergen, Norway, July 5–7, 2000, Lecture notes in computer science, vol 1851. Springer, Berlin, pp 300–313

  • Bárász M, Becker J, Frank A (2005) An algorithm for source location in directed graphs. Oper Res Lett 33:221–230

    Article  Google Scholar 

  • Bartholdi JJ III, Orlin JB, Ratliff HD (1980) Cyclic scheduling via integer programs with circular ones. Oper Res 28:1074–1085

    Article  Google Scholar 

  • Bernáth A (2004/2011) A note on the directed source location algorithm. In: TR-2004-12, Egerváry research group on combinatorial optimization, Budapest, Hungary

  • Bernáth A (2008) Source location in undirected and directed hypergraphs. Oper Res Lett 36:355–360

    Article  Google Scholar 

  • Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4:233–235

    Article  Google Scholar 

  • Daskin MS (1995) Network and discrete location: models, algorithms, and applications. In: Wiley-interscience series in discrete mathematics and optimization. Wiley, New York

  • Fekete Z (2006) Source location with rigidity and tree packing requirements. Oper Res Lett 34:607–612

    Article  Google Scholar 

  • Ford LR, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Oper Res 6:491–433

    Article  Google Scholar 

  • Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton

    Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco

    Google Scholar 

  • Gomory RE, Hu TC (1961) Multi-terminal network flows. J Soc Ind Appl Math 9:551–570

    Article  Google Scholar 

  • Guo J, Niedermeier R (2006) Exact algorithms and applications for tree-like weighted set cover. J Discrete Algorithms 4:608–622

    Article  Google Scholar 

  • Hamacher HW, Heller S, Rupp B (2013) Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning. Ann Oper Res 207:161–180

    Article  Google Scholar 

  • Heller S, Hamacher HW (2011) The multi terminal \(q\)-FlowLoc problem: a heuristic. In: Pahl J, Reiners T, Voß S (eds) Network optimization, Lecture notes in computer science, vol 6701. Springer, Berlin, pp 523–528

  • Heßler P, Hamacher HW (2015) Sink location to find optimal shelters in evacuation planning Eur J Comput Optim (to appear)

  • Ishii T, Fujita H, Nagamochi H (2007) Minimum cost source location problem with local 3-vertex-connectivity requirements. Theor Comput Sci 372:81–93

    Article  Google Scholar 

  • Ishii T (2009) Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs. J Discrete Algorithms 7:570–578

    Article  Google Scholar 

  • Ito H, Ito M, Itatsu Y, Nakai K, Uehara H, Yokoyama M (2002) Source location problems considering vertex-connectivity and edge-connectivity simultaneously. Networks 40:63–70

    Article  Google Scholar 

  • Ito H, Makino K, Arata K, Honami S, Itatsu Y, Fujishige S (2003) Source location problem with flow requirements in directed networks. Optim Methods Softw 18:427–435

    Article  Google Scholar 

  • Ito H, Ito M, Itatsu Y, Uehara H, Yokoyama M (2000) Location problems based on node-connectivity and edge-connectivity between nodes and node-subsets. In: Goos G, Hartmanis J, van Leeuwen J, Lee DT, Teng S-H (eds) ISAAC 2000–algorithms and computation: proceedings of the 11th annual international symposium on algorithms and computation, Taipei, Taiwan, December 18–20, 2000, Lecture notes in computer science, vol 1969. Springer, Berlin, pp 338–349

  • Ito H, Paterson M, Sugihara K (2008) Multi-commodity source location problems and price of greed. In: Nakano S, Rahman MS (eds) WALCOM 2008–algorithms and computation: proceedings of the 2nd international workshop on algorithms and computation, Dhaka, Bangladesh, February 7–8, 2008, Lecture notes in computer science, vol 4921. Springer, Berlin, pp 169–179

  • Ito H, Uehara H, Yokoyama M (2000) A faster and flexible algorithm for a location problem on undirected flow networks. IEICE Trans Fundam Electron Commun Comput Sci E83-A:704–712

  • Kortsarz G, Nutov Z (2008) A note on two source location problems. J Discrete Algorithms 6:520–525

    Article  Google Scholar 

  • Kortsarz, G, Nutov Z (2015) Locating sources to meet connectivity requirements (unpublished manuscript)

  • Nagamochi H, Ishii T, Ito H (2001) Minimum cost source location problem with vertex-connectivity requirements in digraphs. Inf Process Lett 80:287–293

    Article  Google Scholar 

  • Nagamochi H, Ibaraki T (2008) Algorithmic aspects of graph connectivities. Encyclopedia of mathematics and its applications, vol 123. Cambridge University Press, New York

  • Nagamochi H (2004) Graph algorithms for network connectivity problems. J Oper Res Soc Jpn 47:199–223

    Google Scholar 

  • Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York

    Book  Google Scholar 

  • Oxley JG (1992) Matroid theory. Oxford University Press, Oxford

    Google Scholar 

  • Poetranto Groß, D (2008) Network flow and location (FlowLoc): the source location problem. Ph.D. thesis, University of Kaiserslautern, Germany

  • Sakashita M, Makino K, Fujishige S (2008) Minimum cost source location problems with flow requirements. Algorithmica 50:555–583

    Article  Google Scholar 

  • Sakashita M, Makino K, Nagamochi H, Fujishige S (2009) Minimum transversals in posimodular systems. SIAM J Discrete Math 23:858–871

    Article  Google Scholar 

  • Sakashita M, Makino K, Fujishige S (2005) Minimizing a monotone concave function with laminar covering constraints. ISAAC 2005–algorithms and computation: proceedings of the 16th annual international symposium on algorithms and computation, Sanya, China, December 19–21, Lecture notes in computer science, vol 3827. Springer, Berlin, pp 71–81

  • Sakashita M, Makino K, Fujishige S (2006) Minimum cost source location problems with flow requirements. In: Correa JR, Hevia A, Kiwi M (eds) LATIN 2006–theoretical informatics: proceedings of the 7th Latin american symposium on theoretical informatics, Valdivia, Chile, March 20–24, 2006, Lecture notes in computer science, vol 3887. Springer, Berlin, pp 769–780

  • Sugihara K, Ito H (2006a) Maximum-cover source-location problem with objective edge-connectivity three. Electron Notes Discrete Math 25:165–171

  • Sugihara K, Ito H (2006b) Maximum-cover source-location problems. IEICE Trans Fundam Electron Commun Comput Sci E89-A:1370–1377

  • Sugihara K, Ito H (2009) Maximum-cover source-location problems with objective edge-connectivity three. Math Methods Oper Res 70:183–193

    Article  Google Scholar 

  • Tamura H, Sengoku M, Shinoda S, Abe T (1990) Location problems on undirected flow networks. IEICE Trans E73-E:1989–1993

  • Tamura H, Sengoku M, Shinoda S, Abe T (1992) Some covering problems in location theory on flow networks. IEICE Trans Fundam Electron Commun Comput Sci E75-A:678–684

  • Tamura H, Sugawara H, Sengoku M, Shinoda S (1997) On a generalization of a covering problem called single cover on undirected flow networks. IEICE Trans Fundam Electron Commun Comput Sci E80-A:544–550

  • Tamura H, Sugawara H, Sengoku M, Shinoda S (1998) Plural cover problem on undirected flow networks. IEICE Trans Fundam Electron Commun Comput Sci J81-A:863–869

  • Tarjan RE, Yannakakis M (1984) Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs. SIAM J Comput 13:566–579

    Article  Google Scholar 

  • Turner L (2008) Dynamic source location. Diploma thesis, University of Kaiserslautern, Germany

  • van den Heuvel J, Johnson M (2005) The external network problem with edge- or arc-connectivity requirements. CAAN 2004–combinatorial and algorithmic aspects of networking: proceedings of the 1st workshop on combinatorial and algorithmic aspects of networking, Banff, Canada, August 5–7, 2004, Lecture notes in computer science, vol 4405. Springer, Berlin, pp 114–126

  • van den Heuvel J, Johnson M (2008) Transversals of subtree hypergraphs and the source location problem in digraphs. Networks 51:113–119

    Article  Google Scholar 

  • Welsh DJA (1976) Matroid theory. In: L.M.S. Monographs, vol 8. Academic Press, London

  • Yang J, Leung JY-T (2005) A generalization of the weighted set covering problem. Naval Res Logist 52:142–149

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Kaiserslautern, P. O. Box 3049, 67653, Kaiserslautern, Germany

    Lara Turner, Horst W. Hamacher & Sven O. Krumke

  2. INFORM GmbH, Pascalstr. 23, 52076, Aachen, Germany

    Dwi Poetranto Groß

Authors
  1. Lara Turner
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dwi Poetranto Groß
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Horst W. Hamacher
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sven O. Krumke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Horst W. Hamacher.

Additional information

This invited paper is discussed in the comments available at doi:10.1007/s11750-015-0393-9, doi:10.1007/s11750-015-0394-8, doi:10.1007/s11750-015-0396-6, doi:10.1007/s11750-015-0397-5, doi:10.1007/s11750-015-0398-4.

L. Turner, H. W. Hamacher & S. O. Krumke: This research has been partially supported by the European Union Seventh Framework Programme (FP7-PEOPLE-2009-IRSES) under Grant Agreement No. 246647 and by the New Zealand Government as part of the OptALI project. H. W. Hamacher is further supported by the Federal Ministry of Education and Research (BMBF), Germany, Grants 13N12229, 13N12826, and 13N13198.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Turner, L., Groß, D.P., Hamacher, H.W. et al. Static and dynamic source locations in undirected networks. TOP 23, 619–646 (2015). https://doi.org/10.1007/s11750-015-0395-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-015-0395-7

Keywords

Mathematics Subject Classification

Search

Navigation