I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squ …

Title says it all. Why is the choice of data structure for Dijkstra's algorithm a priority queue, rather than a simple sorted list?

In this paper, the author used a variant of lexBFS called lexBFS minus to do the cograph recognition. The implementation of lexBFS in this paper is using Partition Refinement Tec …

Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Fi …

The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the g …

Is there any result about the time complexity of finding a cycle of fixed length k in a general graph? All I know is that Noga Alon et al. use the techinique called "color-coding", …

It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere. You can define a notion of "covering grap …

How fast can an algorithm tell if an integer is square-free? I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and one …

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all …

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region …

Consider the following scenario: We have a number of sequential building blocks (e.g. 12 building blocks, ordered from 1 to 12), distributed randomly (but not necessarily equally …

The classic handshake puzzle goes something like this: "Given that everyone has a different skin disease, how can you safely shake hands with 3 people when you have only 2 glove …

We have a natural number $n>1$. We want to determine whether exists any natural numbers $a, k>1$ such that $n = a^k$. Please suggest a polynomial-time algorithm.

At one point my advisor, Mark Haiman, mentioned that it would be nice if there was a way to compute Groebner bases that takes into account a group action. Does anyone know of a …

I have a question about BigO. I want to know if what im doing is correct in trying to prove these forumlas. Given the question nlogn^8 + n^(3/2) = O(n^(3/2)) I did the following …