Static and dynamic source locations in undirected networks

DOI10.1007/s11750-015-0395-7zbMath1327.90030OpenAlexW2200564040MaRDI QIDQ889101

Horst W. Hamacher, Sven O. Krumke, Dwi Poetranto Groß, Lara Turner

Publication date: 6 November 2015

Published in: Top (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11750-015-0395-7

zbMATH Keywords

matroidNP-hardnesstree networkpseudo-polynomial algorithmfully polynomial-time approximation schemedynamic flowlinear algorithm(dual) greedy algorithm(minimal) deficient setplural cover problemsingle cover problemsource location problemstatic networks

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10) Discrete location and assignment (90B80)

Related Items (2)

Sink location to find optimal shelters in evacuation planning ⋮ On some efficiently solvable classes of the network facility location problem with constraints on the capacities of communication lines

Uses Software

• SITATION
• MOD-DIST
• MENU-OKF

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sink location to find optimal shelters in evacuation planning
• Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning
• Maximum-cover source location problems with objective edge-connectivity three
• Exact algorithms and applications for tree-like Weighted Set Cover
• Source location with rigidity and tree packing requirements
• Minimum cost source location problem with local 3-vertex-connectivity requirements
• Source location in undirected and directed hypergraphs
• A note on two source location problems
• Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs
• Minimum cost source location problem with vertex-connectivity requirements in digraphs
• An algorithm for source location in directed graphs
• Minimum cost source location problems with flow requirements
• Locating Sources to Meet Flow Demands in Undirected Networks
• The Multi Terminal q-FlowLoc Problem: A Heuristic
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three
• Minimum Cost Source Location Problems with Flow Requirements
• Algorithmic Aspects of Graph Connectivity
• Minimum Transversals in Posimodular Systems
• Multi-Terminal Network Flows
• A Greedy Heuristic for the Set-Covering Problem
• Cyclic Scheduling via Integer Programs with Circular Ones
• A generalization of the weighted set covering problem
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Constructing Maximal Dynamic Flows from Static Flows
• Transversals of subtree hypergraphs and the source location problem in digraphs
• Multi-commodity Source Location Problems and Price of Greed
• Algorithms and Computation

This page was built for publication: Static and dynamic source locations in undirected networks