Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!mcnc!duke!srt
From: srt@duke.cs.duke.edu (Stephen R. Tate)
Newsgroups: comp.theory
Subject: Re: Maze searching problem
Message-ID: <11527@duke.cs.duke.edu>
Date: 8 Apr 88 16:30:39 GMT
References: <2119@svax.cs.cornell.edu> <4315@ihlpf.ATT.COM>
Reply-To: srt@duke.UUCP (Stephen R. Tate)
Organization: Duke University, Durham NC
Lines: 18

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