Testing connectivity of faulty networks in sublinear time

DOI10.1016/J.JDA.2011.12.014MaRDI QIDQ450565zbMATH OpenOpenAlexFDO

Authors Tomáš Dvořák, Jiří Fink, Petr Gregor, Václav Koubek, Tomasz Radzik

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

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)

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

Cites work

• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1833092 (Why is no real title available?)
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
• Efficient connectivity testing of hypercubic networks with faults
• On finding a cycle basis with a shortest maximal cycle

Cited in

(3)

• Testing st-Connectivity
• Efficient connectivity testing of hypercubic networks with faults
• Erasure-resilient sublinear-time graph algorithms

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)