Testing connectivity of faulty networks in sublinear time
From MaRDI portal
Publication:450565
DOI10.1016/j.jda.2011.12.014zbMath1248.68374MaRDI QIDQ450565
Tomáš Dvořák, Petr Gregor, Václav Koubek, Tomasz Radzik, Jiří Fink
Publication date: 13 September 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.12.014
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68M15: Reliability, testing and fault tolerance of networks and computer systems
05C40: Connectivity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding a cycle basis with a shortest maximal cycle
- Efficient Connectivity Testing of Hypercubic Networks with Faults
- Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph