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
6
votes
Efficient Hamiltonian cycle algorithms for graph classes
One class of graphs for which many NP-hard problems (including finding a Hamiltonian cycle) are easy (linear-time) are graphs of bounded tree-width. Indeed, by Courcelle's theorem any problem which c …
- 4,713
4
votes
Accepted
Size of forbidden minors for treewidth
Yes, an upperbound was proved in Upper Bounds on the Size of Obstructions and Intertwines by Lagergren. In case you cannot access the paper, the relevant theorem is Theorem 5.9.
If $G$ is an obstruc …
- 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
Accepted
What is the relation between size of maximum clique and branchwidth?
No, your inequality does not hold. You are off by a constant factor. Probably the easiest way to see this is to consider the dual notion of a tangle, which I will define now.
A separation in a graph …
- 32.1k
9
votes
Embedding planar graphs into the grid
As far as I understand, I think you have misstated Valiant's result.
Regarding $1$, yes the embedding is assumed to be planar, with the edges constrained to follow the 'edges' of the grid. This is ca …
- 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
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? …
- 211
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
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