user avatar
user avatar
user avatar
Andrew D. King
  • Member for 11 years, 7 months
  • Last seen more than 1 year ago
14 votes

NP-hard problems on trees

11 votes

Conjectures implying Four Color Theorem

11 votes
Accepted

Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

10 votes

Is feedback vertex set problem is solvable in polynomial time for some special graph

8 votes
Accepted

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

6 votes
Accepted

Decomposition by Clique Separators

5 votes

Approximate graph colouring with a promised upper bound on maximum independent set

5 votes
Accepted

How to find the first $k$ points of high enough level using a priority search tree?

5 votes
Accepted

Finding balanced disjoint cycles in bridgeless cubic graphs

4 votes
Accepted

Given a network flow, are there bounds on the change in weight on nodes?

4 votes

Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

4 votes
Accepted

Combinatorial Independent set Algorithms for sub-classes of perfect graphs

3 votes
Accepted

Max-cut equivalence with most likely assignment to an Ising model

2 votes

Minimum maximal solutions of LPs

2 votes

Maximum-clique practical applications

1 vote

Sorting array of distances by proximity to each other