Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!ucsd!sdcsvax!ucsdhub!ucrmath!marek
From: marek@ucrmath.UUCP (Marek Chrobak)
Newsgroups: comp.theory
Subject: Re: Maze searching problem
Message-ID: <180@ucrmath.UUCP>
Date: 7 Apr 88 18:36:25 GMT
References: <2119@svax.cs.cornell.edu>
Organization: University of California, Riverside
Lines: 28
Keywords: maze, space bound

In article <2119@svax.cs.cornell.edu>, siegel@svax.cs.cornell.edu (Alexander Siegel) writes:
> You are given a graph.  Each graph in the maze is labelled with a name
> of size O(log n).  The graph has the following properties:
> 	1. Each edge is labelled with an arrow but it can be traversed
> 		either direction.
> 	2. The directed graph formed by the arrows is acyclic, and the
> 		in and out-degree if each vertex is at most 2.
> 	3. One vertex is the start and one is the goal.
> 
> The problem is determine whether the goal is reachable from the start
> within an O(log n) space bound and no time bound.

It seems to be equivalent to the reachability problem in general graphs,
even if you restrict the degree of each vertex to 3. The other problem
is open.

Let G = (V,E) be a graph. You can assume that it is already acyclically
oriented (orient {u,v} from the smaller vertex to the bigger one).

Let v \in G. Replace v by two vertices v', v", join the edges incoming
to v to v', the edges outcoming from v to v", and join v to v' (with
direction v-> v'). Now we can replace all edges outcoming
from v" by a binary out-tree, and edges in-coming to v' by a binary
in-tree.

All this can be computed in DLOG.


Marek