Testing connectivity of faulty networks in sublinear time

DOI10.1016/J.JDA.2011.12.014zbMath1248.68374OpenAlexW2003185032MaRDI 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

zbMATH Keywords

connectivityinterconnection networkcycle basisbiconnectivityfaulty vertexvertex expansion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Connectivity (05C40)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Testing connectivity of faulty networks in sublinear time