Snowie
Unregistered
  • Member for 10 years, 11 months
  • Last seen more than 8 years ago
Program for computing Tree decomposition of a graph
22 votes

Some of these software might help you. (Not all of them are open-source though.) *TreeD http://www.itu.dk/people/sathi/treed/ *dlib http://dlib.net/ *QuickBB http://www.cs.washington.edu/homes/...

View answer
Optimal sort algorithm in number of swaps
Accepted answer
15 votes

There exists a stable in-place sorting algorithm with $O(n \log n)$ comparisons and $O(n)$ moves. See: Gianni Franceschini: Sorting Stably, in Place, with $O(n \log n)$ Comparisons and $O(n)$ Moves. ...

View answer
What tools do you use to give presentations?
10 votes

Keynote is one of the popular software, though I use PowerPoint

View answer
What's a good news source for Computer Science?
9 votes

Theory of Computing Blog Aggregator for theoretical computer science

View answer
Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time
Accepted answer
8 votes

There is a sort algorithm with $O(1)$ auxiliary words and achieving $O(n\log n)$ worst-case run time, where $n$ is the length of the input array. http://www.springerlink.com/content/d7348168624070v7/ ...

View answer
Does this bin packing problem have a name?
Accepted answer
8 votes

Your problem is the multiple knapsack problem. Although I am not familiar with this problem, I believe you'll find some papers on your problem, since there are many papers on this problem (see for ...

View answer
bin packing with overlapping objects
Accepted answer
6 votes

Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate. Read this paper for more information: Michael Sindelar, Ramesh K. Sitaraman, ...

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

Strictly speaking, the paper pointed out by singsumit handles the P2P shortest path problem (not the all pairs shortest paths problem). If you really want to compute the all pairs shortest paths ...

View answer
Stable Marriage with incomplete lists and ties - NP-hardness
4 votes

The stable marriage instance with ties is solvable in polynomial time, whereas the stable marriage instance with incomplete lists and ties is NP-hard. The same holds for the Hospitals/Residents ...

View answer
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
4 votes

It is well known that an instance of $n$ men/women can have an exponential number ($O(2^n)$) of stable matchings, but giving a tight upper bound is still open. See Encyclopedia of algorithms http://...

View answer
Natural graphs that are not scale free
3 votes

Although I am not sure what you mean by "random", obvious natural non-scale-free graphs are the road networks.

View answer
Most efficient algorithm to compute set difference?
2 votes

Although many efficient set intersection algorithms have been proposed in the literature, my recommendation is the algorithm proposed in this paper: Bolin Ding, Arnd Christian König: Fast Set ...

View answer
Solving a Min/Max equation set
2 votes

Removing the min/max operations in your problem, you can write your problem in a standard mixed integer programming. If your problem contains $N$ min/max operations, then your problem can be solved ...

View answer
Models of random graphs, for real computer networks
2 votes

My recommendation is the survey paper written by the inventors of the R-MAT random graph generator. http://portal.acm.org/citation.cfm?id=1132954 The R-MAT random graph generator is very simple and ...

View answer
Quality of a conference
-2 votes

I recommend Microsoft Academic Search. See for example: a ranking list for TCS conferences

View answer