NDLI: Traversal of an Unknown Directed Graph by a Finite Robot

Content Provider	Springer Nature Link
Author	Bourdov, I. B.
Copyright Year	2004
Abstract	A covering path in a directed graph is a path passing through all vertices and arcs of the graph, with each arc being traversed only in the direction of its orientation. A covering path exists for any initial vertex only if the graph is strongly connected, i.e., any of its vertices can be reached from any other vertex by some path. The strong connectivity is the only restriction on the considered class of graphs. As is known, on the class of such graphs, the covering path length is Θ(nm), where n is the number of vertices and m is the number of arcs. For any graph, there exists a covering path of length O(nm), and there exist graphs with covering paths of the minimum length Ω(nm). The traversal of an unknown graph implies that the topology of the graph is not a priori known, and we learn it only in the course of traversing the graph. At each vertex, one can see which arcs originate from the vertex, but one can learn to which vertex a given arc leads only after traversing this arc. This is similar to the problem of traversing a maze by a robot in the case where the plan of the maze is not available. If the robot is a “general-purpose computer” without any limitations on the number of its states, then traversal algorithms with the same estimate O(nm) are known. If the number of states is bounded, then this robot is a finite automaton. Such a robot is an analogue of the Turing machine, where the tape is replaced by a graph and the cells are assigned to the graph vertices and arcs. Currently, the lower estimate of the length of the traversal by a finite robot is not known. In 1971, the author of this paper suggested a robot with the traversal length O(nm + n $^{2}$log n). The algorithm of the robot is based on the construction of the output directed spanning tree of the graph and on the breadth-first search (BFS) on this tree. In 1993, Afek and Gafni [1] suggested an algorithm with the same estimate of the covering path length, which was also based on constructing a spanning tree but used the depth-first search (DFS) method. In this paper, an algorithm is suggested that combines the breadth-first search with the backtracking (suggested by Afek and Gafni), which made it possible to reach the estimate O(nm + n $^{2}$loglog n). The robot uses a constant number of memory bits for each vertex and arc of the graph.
Starting Page	188
Ending Page	203
Page Count	16
File Format	PDF
ISSN	03617688
Journal	Programming and Computer Software
Volume Number	30
Issue Number	4
e-ISSN	16083261
Language	English
Publisher	Kluwer Academic Publishers-Plenum Publishers
Publisher Date	2004-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Computer Science Software Engineering/Programming and Operating Systems Operating Systems Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot

Graph Applications in Programming

Parallel computations on a graph

Analysis of a graph by a set of automata

Advances in Robot Programming by Demonstration

Construction of the Algorithm Graph by Autotracing Method

Object-oriented description of graph data structures

Computational programming technologies

A. V. Zamulin

Traversal of an Unknown Directed Graph by a Finite Robot

Similar Documents

Backtracking Problem in the Traversal of an Unknown Directed Graph by a Finite Robot

Graph Applications in Programming

Parallel computations on a graph

Analysis of a graph by a set of automata

Advances in Robot Programming by Demonstration

Construction of the Algorithm Graph by Autotracing Method

Object-oriented description of graph data structures

Computational programming technologies

A. V. Zamulin

Traversal of an Unknown Directed Graph by a Finite Robot