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.
0
votes
Enumerate spanning trees
Contract $e_1$ and delete $e_2$. Say $G$ is the original graph and $H$ is the new graph. Now run the tree enumeration algorithm on $H$. After reversing the contraction, you get all the spanning trees …
- 37.7k
2
votes
Calculating variance-minimal perfect matchings
If the edge weights are scaled by a sufficiently high factor, a minimum weight matching will have the least greatest weight. By also removing the edges with weight less than $w$, a minimum weight matc …
- 37.7k
0
votes
Graph vertices selection for paths sum minimalization
Your description is unclear, so I'm guessing a bit.
First, make a weighted complete graph $K$, where the weight of edge $ij$ is the distance in $G$ from $i$ to $j$.
Now you want a minimum weight perfe …
- 37.7k
1
vote
Accepted
Methods to solve for a matrix whose entries satisfy certain properties
There are zero or infinitely many solutions depending on where the non-zero entries have to be. So there is no general-purpose answer.
I don't think your equations are properly stated, as $\boldsymbol …
- 37.7k
3
votes
Accepted
Do all graphs with $n$ vertices and $m$ edges have a special property?
Regarding practical algorithms for graphs of about this size, first note that if there is a large enough bipartite subgraph then there is one with the smallest side at most 6 vertices. …
- 37.7k
4
votes
Accepted
Interpreting optimal matchings as permutations
$$\pmatrix{ 2&3&0&0\\0&2&3&0\\0&0&2&3\\3&0&0&2}$$
Every swap of two columns or swap of two rows decreases the trace. However, there is a permutation putting all the 3s on the diagonal.
- 37.7k
3
votes
An efficient generalized algorithm to obtain an arbitrary element of a lexicographically ord...
If the efficiency is very important for you, you should consider if you really need lexicographic order. Other orders have slightly faster unranking. For example, I like this one for subsets of size …
- 37.7k
1
vote
Make $n$ numbers equal using pairwise averages
Too long for a comment.
Without loss of generality, we can assume the numbers are integers. I'll show that one can always achieve an integer multiset with only two values.
For a multiset $Y=\{\!\{ y_1 …
- 37.7k
5
votes
Accepted
Algorithm to calculate edge orbits of a graph
The automorphism group is defined to be a permutation group acting as permutations of the vertices. It induces a permutation group acting as permutations of the edges: $\pi:V\to V$ induces $\pi:E\to E …
- 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
2
votes
Accepted
The complexity of expansion ratio (Cheeger constant) of a graph
This paper says it is NP-hard and gives three references.
- 37.7k
2
votes
Accepted
A fast algorithm for a probabilistic counting problem without replacement?
I'm not sure why you ask for "distinct integers" when sampling without replacement guarantees distinctness.
Let $q_i=1-p_i$. The ordinary generating function
$$F(u,y) = \prod_{i=1}^n (q_i+p_i uy) \pr …
- 37.7k
3
votes
Accepted
Calculating the values of a generalization of binomials to permutations
It is a $k\times n$ latin rectangle: write the permutations one per row.
This paper has a nice summary of theoretical and practical methods.
The sum of the permutation matrices can be interpreted as …
- 37.7k
2
votes
Accepted
Matrix completion problem with determinant condition?
I will prove it is NP-complete if $T$ is restricted to $\pm 1$.
Let $k_1,\ldots,k_n$ be an arbitrary list of integers.
Suppose the cofactors of $L$ along the top row are $c_1,\ldots,c_n$ and all not …
- 37.7k
4
votes
Accepted
Algorithm to decide if the union of a set system covers the power set
Given $T_k = [m_k,M_k]$ and $X\subseteq [n]$, it is easy to calculate the number of sets in $T_k$ that contain $X$: $$Q_{X,k}=|\{T\in T_k \mid X\subseteq T\rbrace|.$$
So start with $\sum_k Q_{\emptys …
- 37.7k