Testing connectivity of faulty networks in sublinear time

DOI10.1016/J.JDA.2011.12.014zbMATH Open1248.68374OpenAlexW2003185032MaRDI QIDQ450565FDOQ450565

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

Recommendations

• Efficient connectivity testing of hypercubic networks with faults
• Property testing on \(k\)-vertex-connectivity of graphs
• Property Testing on k-Vertex-Connectivity of Graphs
• Property testing in bounded degree graphs
• Distributed edge connectivity in sublinear time

zbMATH Keywords

biconnectivityconnectivityinterconnection networkfaulty vertexcycle basisvertex expansion

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Title not available (Why is that?)
• On finding a cycle basis with a shortest maximal cycle
• Efficient Connectivity Testing of Hypercubic Networks with Faults
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Title not available (Why is that?)

Cited In (1)

• Testing st-Connectivity

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

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