New data structures for subgraph connectivity

DOI10.1007/978-3-642-14165-2_18MaRDI QIDQ3587380zbMATH OpenOpenAlexFDO

Authors Ran Duan

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14165-2_18

Mathematics Subject Classification ID

Connectivity (05C40) Data structures (68P05)

Recommendations

• Faster randomized worst-case update time for dynamic subgraph connectivity
• Dynamic Subgraph Connectivity with Geometric Applications
• Dynamic connectivity: connecting to networks and geometry
• Faster worst case deterministic dynamic connectivity
• Dynamic graph connectivity in polylogarithmic worst case time

Cited in

(14)

• Faster randomized worst-case update time for dynamic subgraph connectivity
• A dynamic data structure for counting subgraphs in sparse graphs
• Dynamic connectivity: connecting to networks and geometry
• Connectivity oracles for graphs subject to vertex failures
• Dynamic Subgraph Connectivity with Geometric Applications
• scientific article; zbMATH DE number 1941159 (Why is no real title available?)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Incremental and fully dynamic subgraph connectivity for emergency planning
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Fully dynamic connectivity oracles under general vertex updates
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Don't rush into a union, take time to find your roots
• On the complexity of algorithms with predictions for dynamic graph problems
• Connectivity oracles for predictable vertex failures

This page was built for publication: New data structures for subgraph connectivity

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