Live briefing
Everything about Reachability
Whether one vertex can be reached from another in a graph
In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex if there exists a sequence of adjacent vertices which starts with and ends with. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: ReachabilityA 5-minute orientation
- Skim a recent paper: Data-Driven Safety Filters: Hamilton-Jacobi Reachability, Control Barrier Functions, and Predictive Methods for Uncertain SystemsInfluential work since 2022
- Pick up a classic book: Reachability ProblemsThe most-reprinted book on the subject
- Read the landmark paper: Controllers for reachability specifications for hybrid systemsCited 463 times
- Go sideways: Planar separator theoremA closely related topic
- Go sideways: Karger's algorithmA closely related topic
📖 Definitions
Noun The condition of being reachable
Noun The extent to which a node in a graph is reachable from others
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Controllers for reachability specifications for hybrid systems
Controllability and reachability criteria for switched linear systems
Reachability and Distance Queries via 2-Hop Labels
Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems
Online Verification of Automated Road Vehicles Using Reachability Analysis
On the minimax reachability of target sets and target tubes
An Algorithm for the General Petri Net Reachability Problem
Size-Estimation Framework with Applications to Transitive Closure and Reachability
🆕 Influential since 2022
Data-Driven Safety Filters: Hamilton-Jacobi Reachability, Control Barrier Functions, and Predictive Methods for Uncertain Systems
Bilinearization, Reachability, and Optimal Control of Control-Affine Nonlinear Systems: A Koopman Spectral Approach
Data-Driven Reachability Analysis From Noisy Data
Ellipsotopes: Uniting Ellipsoids and Zonotopes for Reachability Analysis and Fault Detection
Robot Learning of Mobile Manipulation With Reachability Behavior Priors
📚 Books worth reading
Reachability ProblemsParosh Aziz Abdulla, Igor Potapov · 2010
Validation of communications systems with SDLLaurent Doldi · 2003- 📕Supervisory Control and Scheduling of Resource Allocation SystemsBo Huang, MengChu Zhou · 2020
Reachable StarsGeorge E. Lankford · 2007
Stochastic reachability analysis of hybrid systemsLuminita Manuela Bujorianu · 2012- 📕ReachableJeffery D. Skinner · 2024
- 📕Reachable Sets of Dynamic SystemsStanislaw Raczynski · 2023
Reachability ProblemsAlain Finkel · 2012
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Planar separator theorem In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into…
- Karger's algorithm In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David…
- Parallel algorithms for minimum spanning trees In graph theory a minimum spanning tree (MST) T {\displaystyle T} of a graph G = ( V , E ) {\displaystyle G=(V,E)} with | V | = n {\displaystyle |V|=n}…
- Graph bandwidth In graph theory, the graph bandwidth problem may be visualized as placing the vertices of a given graph at distinct integer positions along the number…
- Savitch's theorem In computational complexity theory, Savitch's theorem, proved by Walter Savitch in 1970, gives a relationship between deterministic and non-deterministic…
- Fractional cascading In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures…
- Kernelization In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which…
- Wiener connector In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected…