• Member for 10 years, 10 months
  • Last seen more than 5 years ago
Connectivity Problem
Accepted answer
8 votes

Maximize Edge Disjoint Paths (EDP) The problem is NP Hard and here are some results: 1) It accepts $O(\sqrt{m})$ approximation by Kleinberg in 96 in general graphs. 2) The above is tight for ...

View answer
All pair shortest path problem for large number of nodes
6 votes

Search papers on : "Shortest Path Queries Using Highway Hierarchies". There is a paper by Sanders and Schultes. If you follow their citations, there are lot of other papers. These methods are very ...

View answer
Amortized Analysis
3 votes

I am again restating what has been said. The amortized analysis formally introduced by Robert Tarjan involves considering the whole sequence of operation throughout the algorithm. The analysis is ...

View answer
Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm
1 votes

im not sure about the answer (haven't gone through paper) but i think this should help. The numbers are packed into a single word, so operations on a single word take O(1) time. If there are, say, k ...

View answer