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 2233
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.
5
votes
Accepted
Approximation of Hamiltonian cycles
Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP.
Proof. Let $G$ be an instance of the Travelling Salesman Problem (TS …
- 32.1k
2
votes
Accepted
Algorithm for finding a minimum weight circuit in a weighted binary matroid
The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is t …
- 32.1k
4
votes
Accepted
Efficient algorithm for edge-coloring complete graphs
Yes, for all $n$, the edge-chromatic number of $K_{2n}$ is $2n-1$ and the edge-chromatic number of $K_{2n+1}$ is $2n+1$. Moreover, it is easy to construct such edge-colourings in polynomial time. Fo …
- 32.1k
2
votes
Accepted
$W[1]$-hard and FPT about the equitable tree-coloring problem
No. Fix $k \in \mathbb{N}$ and let $G$ be an $n$-vertex graph of treewidth at most $k$. If you analyze their polynomial-time algorithm that decides if $G$ has an equitable tree-colouring, you'll noti …
- 32.1k
6
votes
Distinct numbers in multiplication table
They note that for larger values of $n$, exact algorithms become impractical, and so the paper also presents two Monte Carlo algorithms to approximate $M(n)$. …
- 32.1k
4
votes
Polynomial time algorithm for rigid graph isomorphism
It is a long standing open question if graph isomorphism can be solved in polynomial time when the input graphs are rigid. See here, for example.
So, if correct, your algorithm would be a major breakt …
- 32.1k
2
votes
Coloring infinite graph made out of copies of a finite graph
Here is how to reduce the problem to a finite colouring problem.
Let $G'=G_0 \cup \dots \cup G_K$. For each $t \in \mathbb{N}$, the $tG'$ be the subgraph of $G^\infty$ consisting of $t$ consecutive co …
- 32.1k
2
votes
What is the complexity of a special multigraph edge coloring problem
I strongly suspect that this is NP-complete, but the approach I have in mind does not seem to work! I wanted to use the the well-known fact that it is NP-complete to decide whether the chromatic inde …
- 32.1k
1
vote
Examples of Super-polynomial time algorithmic/induction proofs?
Another example is the matroid intersection theorem, which is a rich source of min/max theorems in combinatorial optimzation. For example, it includes your example (Kőnig's theorem) as a special case …
- 32.1k
10
votes
2
answers
590
views
Transfinite algorithms
Note that (3) is in contrast to algorithms which do not terminate because they cycle, such as certain pivoting rules of the Simplex algorithm. … Are there other examples of non-terminating algorithms which satisfy properties (1), (2), and (3)? If so, have their ordinal run-times been analyzed? …
- 32.1k
2
votes
Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges
The problem is NP-hard, even in the unweighted case (all weights equal to $1$).
Indeed, given a graph $G$ and an integer $k$, deciding if $G$ contains an Eulerian subgraph with at least $k$ edges is N …
- 32.1k
1
vote
Accepted
Partitioning vertex set to maximize weights of inter-class edges?
This is the weighted MAX CUT problem, and it is NP-hard to compute exactly. Note that the case of $\{0,1\}$-weights corresponds to computing a MAX CUT in an arbitrary graph. This later problem has a …
- 32.1k
7
votes
(Non)uniqueness of the common-factor graph
The answer to Q1 is yes. We proceed by induction on $|E(G)|$. For the base case, assign distinct primes to each vertex.
For the inductive step, choose a non-isolated vertex $v$. By induction, $G-v …
- 32.1k
2
votes
Accepted
3-Approximation Algorithm for 3-Hitting Set
Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. Rephrased, our goal is to find …
- 32.1k
4
votes
Accepted
2-approximation algorithm for Minimum Maximal Matching (MMM) problem
There is an easy $2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching $M$ can be found greedily. Initialize $M=\em …
- 32.1k