Tag Info

New answers tagged

0

In the same spirit of Sanjeev Arora's notes that @umar posted, I like Madhur Tulsiani's lecture notes and exercises for his "Mathematical Toolkit" class posted at the course webpage. In addition to Arora's excellent material his notes have a nice coverage of spectral graph theory as well as the multiplicative weights update method.


2

In Victor Teixeira de Almeida, Ralf Hartmut Güting: Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases. SAC 2006: 58-62, Teixeira and Güting describe a new storage schema with a set of indexed structures to support an efficient execution of a slightly modified version of the Dijkstra's algorithm. In the ...


2

Maybe I miss something, but it looks obvious that if $k<=n$ then you can rearrange the objects in the simplest way. Number the objects of each bin from 0 to k-1 and move object i to the i'th next bin. Before: bin A: {A0, A1, A2} bin B: {B0, B1, B2} bin C: {C0, C1, C2} bin D: {D0, D1, D2} After: bin A: {A0, D1, C2} bin B: {B0, A1, D2} bin C: {C0, B1, ...


2

Question 1: No counterexample: bin 1 = $[1,2,3]$, bin 2 = $[4,5,6]$


11

If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see ...


14

The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in: Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421 (1979) From the paper: ... 4. Some #P-complete problems ... 14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected) Input: $G; s,t ...


1

research on graph isomorphism has generally gone in the direction of looking at efficient or improved algorithms for many special graph classes with P-Time algorithms for which there has been much progress, and also more empirical analysis with state-of-the-art software eg Nauty looking somewhat at average and worst case behaviors separately. for the general ...



Top 50 recent answers are included