Exploration of Faulty Hamiltonian Graphs

DOI10.1142/S0129054116500313MaRDI QIDQ2970203zbMATH OpenOpenAlexFDO

Authors David Caissy, Andrzej Pelc

Publication date 28 March 2017

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.05136

zbMATH Keywords

algorithmexplorationfaulty edgeHamiltonian graphmobile agent

Mathematics Subject Classification ID

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

Abstract: We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An exploration algorithm, for a given network and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm.

Recommendations

• Construction schemes for fault-tolerant Hamiltonian graphs
• Hamiltonian cycles in hypercubes with faulty edges
• On some super fault-tolerant Hamiltonian graphs
• Conditional fault Hamiltonicity of the complete graph
• Hamiltonian cycles in hypercubes with more faulty edges
• Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
• Hamiltonicity of hypercubes with faulty vertices
• Hamiltonian graphs with minimum number of edges for fault-tolerant topologies

Cites work

• Approximation bounds for Black Hole Search problems
• Black hole search in common interconnection networks
• Deterministic network exploration by a single agent with Byzantine tokens
• Efficient exploration of faulty trees
• Efficient grid exploration with a stationary token
• Exploring an unknown dangerous graph using tokens
• Exploring an unknown graph
• Exploring Unknown Environments
• Exploring Unknown Undirected Graphs
• Fault-tolerant sequential scan
• Hardness and approximation results for black hole search in arbitrary networks
• How to learn an unknown environment. I
• Locating and repairing faults in a network with mobile agents
• Mobile search for a black hole in an anonymous ring
• Navigating in Unfamiliar Geometric Terrain
• Online Navigation in a Room
• Optimal constrained graph exploration
• Optimal graph exploration without good maps
• Piecemeal graph exploration by a mobile robot.
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for black holes in subways
• The power of a pebble: Exploring and mapping directed graphs
• Tree exploration with little memory

Cited in

(2)

• Vertex-ant-walk -- a robust method for efficient exploration of faulty graphs
• Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots

This page was built for publication: Exploration of Faulty Hamiltonian Graphs

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