siegel@svax.cs.cornell.edu (Alexander Siegel) (04/06/88)
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.
Note: an equivalent problem is to produce a new graph such that the only
vertex with in-degree 0 is the start, and the head can only move
to the right on the output tape.
--
Alex Siegel
(607)255-1165 (Low Bandwidth Audio)
4161 Upson Hall, Cornell University, Ithaca NY 14853 (Hard Copy)
siegel@svax.cs.cornell.edu (ARPAnet)
siegel@CRNLCS (BITNET)
{uw-beaver,ihnp4,decvax,vax135}!cornell!siegel (UUCP)crocker@ihlpf.ATT.COM (Crocker) (04/07/88)
Is n the number of vertices in the graph (v), number of edges in the graph (e), number of *things* in the graph (v+e), or something completely different? Ron Crocker AT&T Bell Laboratories (312) 416-5262 -- Ron Crocker IHP 1A-213 x5262
marek@ucrmath.UUCP (Marek Chrobak) (04/08/88)
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
siegel@SVAX.CS.CORNELL.EDU (Alexander Siegel) (04/08/88)
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.
Note: an equivalent problem is to produce a new graph such that the only
vertex with in-degree 0 is the start, and the head can only move
to the right on the output tape.
--
Alex Siegel
(607)255-1165 (Low Bandwidth Audio)
4161 Upson Hall, Cornell University, Ithaca NY 14853 (Hard Copy)
siegel@svax.cs.cornell.edu (ARPAnet)
siegel@CRNLCS (BITNET)
{uw-beaver,ihnp4,decvax,vax135}!cornell!siegel (UUCP)pase@ogcvax.UUCP (Douglas M. Pase) (04/08/88)
In article <svax.2119> 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 a simple dynamic programming approach would solve this easily.
It also seems that it would solve it in time proportional to n times the
distance between the start and the goal. What's more, it would be independent
of any cycles, no matter how contorted. I suppose whether this is true might
depend *how* the graph is represented. If it is represented by a transition
matrix then a dynamic programming approach would certainly be more than
adequate.
--
Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@cse.ogc.edu (CSNet)srt@duke.cs.duke.edu (Stephen R. Tate) (04/08/88)
In article <4315@ihlpf.ATT.COM> crocker@ihlpf.ATT.COM (Crocker) writes: >Is n the number of vertices in the graph (v), number of edges in >the graph (e), number of *things* in the graph (v+e), or something >completely different? > Does it really matter? Since each vertex has constant-bounded degree, all the things you mentioned are equivalent. (all are O(n)) Also, in response to someone else's posting about dynamic programming: Fine and dandy, but the original question was asking about keeping the space to O(log n). The dynamic programming approach would take considerably more space than that. -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt@cs.duke.edu
pase@ogcvax.UUCP (Douglas M. Pase) (04/09/88)
In article <ogcvax.1613> pase@ogcvax.UUCP (Douglas M. Pase) writes:
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 a simple dynamic programming approach would solve this easily.
OOPS... dynamic programming would use O(n) space.
--
Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@cse.ogc.edu (CSNet)