bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 5 years, 2 months |
seen | Apr 30 at 20:12 | |
stats | profile views | 1,305 |
I am interested in graph theory and combinatorial optimization.
Feb 21 |
revised |
A k-1 edge connected k regular graph is matching covered
added 1113 characters in body |
Jan 6 |
comment |
Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function
So in other words, the line for $y$ is "glued to" the window, and you move the window along the $x$-axis? |
Jan 6 |
comment |
Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function
Can you use $\Theta(n)$ storage? Why not just make a queue of squares of differences. When you advance the window by 1, simply add the new square difference and subtract the square distance that disappears from the window. This is constant time per step once you spend $O(n)$ time setting up the initial window. Or do you mean that the window is moved to some position arbitrarily far away? |
Dec 9 |
comment |
Characteristics of locally triangle-free graph
This is a comment instead of an answer since I omit so many details. It's fairly easy to see that $G$ can be any tree. Fix a root and lay out the tree in such a way that the angle between any two children of a vertex is very small. If you do this with increasingly small angles as you move away from the root, you can complete the triangulation using points on an arc very far away from the tree, so that the tree is at the centre of the circle containing the arc. I believe it should be straightforward to modify the construction so that $G$ can actually be any acyclic graph. |
Nov 21 |
comment |
SWAT vs Rioters (cops vs robbers variant)
If it is no, then see what happens for chordal graphs, then graphs of bounded treewidth. |
Nov 21 |
comment |
SWAT vs Rioters (cops vs robbers variant)
Just a few thoughts. First, it is probably best, at least to start, to insist that $S$ and $R$ are increasing functions. It seems like the graph should be SWAT-win if SWAT can eradicate the rioters given any initial configuration. Characterizing SWAT-win graphs in a very general way seems very difficult, so I would start with the obvious first steps: Trees, cycles, outerplanar graphs. Then a first question becomes: Given a weighted graph and initial numbers of SWAT/Rioters, can we determine if it is SWAT-win in polynomial time? I suspect the answer is no, but I'm not sure. |
Nov 8 |
comment |
probability distribution of hitting nodes on a finite graph random walk
Also sometimes known as small world graphs. |
Oct 24 |
answered | A k-1 edge connected k regular graph is matching covered |
Oct 18 |
comment |
Has anyone seen this graph?
In particular this graph is the smallest simple cubic graph with no perfect matching. |
Oct 17 |
comment |
What is this subclass of $k$-colorable graphs called?
I would call such a graph edge-maximal $k$-colourable. This property can be useful in induction on the number of non-edges in a graph. |
Aug 31 |
awarded | Necromancer |
Jul 27 |
comment |
Can you prove that hypergraphs with n-1 edges are partially 2 colorable?
Good! I was a little worried that Hall's theorem was the theorem you wanted to avoid. |
Jul 27 |
answered | Can you prove that hypergraphs with n-1 edges are partially 2 colorable? |
Jul 7 |
awarded | Critic |
Jun 15 |
comment |
Fast removal of weighted edges in a graph in a way such that all shortest paths are preserved
So is this equivalent to computing all-pairs shortest path, then deleting all edges not contained in some shortest path? And I don't really understand the question... use the Floyd-Warshall algorithm if you want it to be simple, and use this Sudakov result you mention if you want it to be fast. I highly doubt that you would easily be able to construct the edge set faster than that, but I may be wrong. |
Jun 13 |
answered | Combinatorial Proof of Weak Perfect Graph Theorem. |
Apr 22 |
comment |
Probability of having a bounded ratio of two types of balls in each of 'S' bins after random partitioning of a fixed number of balls
I agree with Peter. For certain values of $S$, $L$, and $A$, the Chernoff bound seems like it would be more than sufficient. |
Mar 13 |
awarded | Yearling |
Feb 12 |
comment |
Maximal clique intersection graphs
Thanks for this link... it may be useful for me, as I am also interested in maximal clique graphs (for different reasons). |
Feb 9 |
answered | Reasonable “Random” matrices to test numerical algorithms |