The searchlight problem for road networks

DOI10.1016/J.TCS.2015.04.026MaRDI QIDQ2354403zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Hirotaka Ono, Ichiro Suzuki, Łukasz Wrona, Masafumi Yamashita, Paweł Żyliński

Publication date 13 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.04.026

zbMATH Keywords

gridsline segmentslinesgraph searchingsearchlight problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An efficient search algorithm for road network optimization
• The shortest path problem on large-scale real-road networks
• Finding \(K\) shortest looping paths in a traffic-light network
• Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights
• Search for \(C\)-optimal routes in graphs
• Partial outer convexification for traffic light optimization in road networks

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 6257577 (Why is no real title available?)
• A complete algorithm for searchlight scheduling
• A pursuit-evasion problem on a grid
• An annotated bibliography on guaranteed graph searching
• An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs
• An optimal algorithm for solving the searchlight guarding problem on weighted two-terminal series-parallel graphs
• Bushiness and a tight worst-case upper bound on the search number of a simple polygon.
• CLEARING A POLYGON WITH TWO 1-SEARCHERS
• Cooperative mobile guards in grids
• Covering grids and orthogonal polygons with periscope guards
• Finding the minimum-distance schedule for a boundary searcher with a flashlight
• Guarding a set of line segments in the plane
• Illuminating disjoint line segments in the plane
• Illumination in the presence of opaque line segments in the plane
• On gallery watchmen in grids
• Optimal Algorithms for a Pursuit-Evasion Problem in Grids
• Searching a polygonal region by a group of stationary \(k\)-searchers
• Searching and pebbling
• Searching for a Mobile Intruder in a Polygonal Region
• Searching polyhedra by rotating half-planes
• Some pursuit-evasion problems on grids
• THE MINIMUM GUARDING TREE PROBLEM
• The Searchlight Scheduling Problem
• The complexity of searching a graph
• Vision-based pursuit-evasion in a grid
• Watchman routes for lines and line segments

Cited in

(2)

• An efficient search algorithm for road network optimization
• Dominating vertex covers: the vertex-edge domination problem

This page was built for publication: The searchlight problem for road networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354403)