From eppstein@euclid.ics.uci.edu Tue Apr 27 20:10:12 CDT 1999 Article: 247649 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!uchinews2!newsfeed.berkeley.edu!awabi.library.ucla.edu!134.139.1.31!csulb.edu!drivel.ics.uci.edu!euclid.ics.uci.edu!not-for-mail From: eppstein@euclid.ics.uci.edu (David Eppstein) Newsgroups: sci.math Subject: Re: Network Flows on planar graphs. Date: 20 Apr 1999 23:50:05 -0700 Organization: UC Irvine Department of ICS Lines: 30 Message-ID: <7fjset$5n5@euclid.ics.uci.edu> References: <371C7ADB.6075DAB2@mailcity.com> <7fi6oo$4vk@euclid.ics.uci.edu> <371D502F.F1E38E47@mailcity.com> NNTP-Posting-Host: euclid.ics.uci.edu X-Newsreader: NN version 6.5.1 (NOV) Xref: news.math.niu.edu sci.math:247649 In <371D502F.F1E38E47@mailcity.com> Dr Acula writes: > Thanx a lot David for that reference. Could u tell me where the > repository of com sci papers are kept and what indexes we can use to > search in that repository? In this particular case the index was in my head, and I found the detailed reference by searching some files of mine for the authors' names which I already knew. But a more useful answer to your question is http://liinwww.ira.uka.de/bibliography/index.html Mostly when I do my searches I use other databases: INSPEC, MathSci, or WebOfScience, but those are all subscription-only. > (for instance what did u choose for getting Linear time MST for planar > graphs?) Did you mean MST or shortest path here? The ref I gave you was for shortest paths. I'm not sure what you mean by "what did u choose", but the linear time planar MST result is unfortunately sort of folklore without a good reference. I think the usual paper people cite for it is Cheriton and Tarjan (too lazy to look up the full reference for you, consider this an opportunity to try the URL I just gave you). But, Boruvka's algorithm dating back to the 1930s will work if you just use bucket sort or something to clean out the duplicate edges (insert long flamewar with NMM about how bucket sort isn't really linear). -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/