Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options not deleted
user 9025
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
25
votes
3
answers
1k
views
Changing the signs of the coefficients of a polynomial to make all the roots real
We are given a polynomial
$$P_n(x):=a_nx^n + a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$
with real coefficients.
Questions.
$\boldsymbol{(i)}$ How can we determine if there are $\epsilon_1,\ldots,\eps …
- 37.7k
19
votes
Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?
Johnson graphs do not cause difficulty to existing programs. Actually they are rather easy; nauty can handle them up to tens of millions of vertices, and so can other programs such as Traces and Bliss …
- 37.7k
17
votes
Algorithms for calculating R(5,5) and R(6,6)
I'm not sure we could find $R(5,5)$ in one year, because exhaustive search is infeasible and one year is probably not enough time to develop the extra theory that would make it possible.
I'll dispose …
- 37.7k
14
votes
Accepted
Is there an efficient algorithm to check whether a matrix is symmetrizable using only permut...
The problem is NP-complete, see C. Colbourn and B. D. McKay, A correction to Colbourn's paper on the complexity of matrix symmetrizability, Information Processing Letters, 11 (1980) 96-97. Here is a s …
- 37.7k
12
votes
Accepted
How many edge-disjoint cycles of length 3 are in the complete graph?
The maximum number of edge-disjoint triangles in a complete graph is determined by:
Joel Spencer.
Maximal consistent families of triples.
J. Combinatorial Theory, 5 1968 1–8.
- 37.7k
10
votes
How can I produce 'canonical' forms for rooted bipartite graphs?
This problem is algorithmically equivalent to the general problem of finding a canonical labelling for a graph. To see that, take an arbitrary graph, add a new vertex adjacent to everything and call i …
- 37.7k
10
votes
1
answer
410
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair …
- 37.7k
9
votes
2
answers
353
views
Finding local patterns in a circular list
Consider a list $\boldsymbol{x}=x_0,x_1,\ldots,x_{n-1}$, which we consider to be circular by taking the subscripts modulo $n$. The entries in the list are distinct integers.
A local pattern is a Boo …
- 37.7k
8
votes
Polynomial time algorithm for rigid graph isomorphism
You have reduced the graph isomorphism problem to a 0-1 programming problem. 0-1 programming problems are NP-hard in general, so the question is whether your particular case is an exception. You haven …
- 37.7k
8
votes
Accepted
Details of generation programs supplied with nauty
MathOverflow is not a good place for questions like this. The best place for technical questions about nauty is the mailing list.
Anyway, the parent of a graph $G$ is a graph $G-v$ where $v$ is some …
- 37.7k
8
votes
Algorithms for finding graph isomorphisms
Nauty and Traces
Bliss
Saucy
Conauto
VF2
To be taken seriously as a competitor you should be able to perform well on at least some of the difficult graph classes collected by Adolfo Piperno.
- 37.7k
8
votes
Is there a way of canonically labelling permutation groups?
This seems to be one of the biggest holes in the practical isomorphism arsenal. Various non-trivial possibilities come to mind, but their efficiency relies a lot on a more basic question. Define (and …
- 37.7k
7
votes
Accepted
Is it possible to decide in polynomial time if a poset is a subposet of another which is giv...
Completing Emil's observation: Take any subgraph isomorphism problem (well known to be NP-complete). Add a new vertex in the middle of each edge and then orient the new edges outwards from the new ve …
- 37.7k
7
votes
0
answers
181
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ nei …
- 37.7k
6
votes
Accepted
Algorithm to find if an element X can be represented with the sum of one number of each subs...
First sort $S_2$ and $S_3$.
Divide into $n$ subproblems: for each $a\in S_1$, look for $b\in S_2,c\in S_3$ such that $b+c=X-a$. Let's do one such subproblem in $O(n)$ time.
Let $b_j$ be the $j$-th …
- 37.7k