Article View: comp.theory
Article #1962Re: Maze searching problem
From: Stephen R. Tate
Date: Fri, 08 Apr 1988 16:30
Date: Fri, 08 Apr 1988 16:30
18 lines
1122 bytes
1122 bytes
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
Technical Details
Message-ID:
<11527@duke.cs.duke.edu>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!mcnc!duke!srtReferences:
<2119@svax.cs.cornell.edu> <4315@ihlpf.ATT.COM>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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