Article View: comp.theory
Article #1964Maze searching problem
From: Alexander Siegel
Date: Thu, 07 Apr 1988 18:53
Date: Thu, 07 Apr 1988 18:53
21 lines
1511 bytes
1511 bytes
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)
Technical Details
Message-ID:
<8804071921.AA08296@jade.berkeley.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!husc6!uwvax!dogie!uwmcsd1!ig!agate!ucbvax!SVAX.CS.CORNELL.EDU!siegelShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!att-cb!osu-cis!tut.cis.ohio-state.edu!husc6!uwvax!dogie!uwmcsd1!ig!agate!ucbvax!SVAX.CS.CORNELL.EDU!siegel
From: siegel@SVAX.CS.CORNELL.EDU (Alexander Siegel)
Newsgroups: comp.theory
Subject: Maze searching problem
Message-ID: <8804071921.AA08296@jade.berkeley.edu>
Date: 7 Apr 88 18:53:13 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: TheoryNet List <THEORYNT%NDSUVM1.bitnet@jade.berkeley.edu>,
Alexander Siegel <siegel@svax.cs.cornell.edu>
Distribution: inet
Organization: The Internet
Lines: 21