Reachability in graph timelines

DOI10.1145/2422436.2422468MaRDI QIDQ2986875zbMATH OpenOpenAlexFDO

Authors Jakub Łącki, Piotr Sankowski

Publication date 16 May 2017

Published in Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2422436.2422468

zbMATH Keywords

dynamic graph algorithmsgraph timelinereachabilitytransitive closure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Fast and Simple Connectivity in Graph Timelines
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Improved Dynamic Reachability Algorithms for Directed Graphs
• scientific article; zbMATH DE number 2079364

Cites work

• A model of interactive teaching
• A theory of goal-oriented communication
• A theory of the learnable
• Algorithmic Learning Theory
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 3154781 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 67631 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Learning from different teachers
• Measuring teachability using variants of the teaching dimension
• Models of cooperative teaching and learning
• Occam's razor
• On specifying Boolean functions by labelled examples
• On the complexity of teaching
• On the limits of efficient teachability
• On the power of inductive inference from good examples
• Pseudorandom generators for space-bounded computation
• Recent Developments in Algorithmic Teaching
• Teachability in computational learning
• Teaching a smarter learner.
• Teaching Randomized Learners

Cited in

(7)

• Observability of extended timed event graph
• Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• scientific article; zbMATH DE number 5885701 (Why is no real title available?)
• Fast and Simple Connectivity in Graph Timelines
• Algorithms for Extracting Timeliness Graphs
• scientific article; zbMATH DE number 5587270 (Why is no real title available?)

This page was built for publication: Reachability in graph timelines

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