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.
36
votes
Accepted
Can one measure the infeasibility of four color proofs?
To answer the question it is important to disentangle the proof as follows.
Theorem 1. Every minimum counterexample to the 4CT is an internally 6-connected triangulation.
Theorem 2. If $T$ is a min …
- 32.1k
15
votes
Choosing two-colorable subgraph in a triangulation
Yes, such a subgraph always exist. Let $G$ be a planar triangulation. By the $4$-colour theorem, $G$ has a $4$-colouring. We let $H$ be the subgraph consisting of all edges with endpoints coloured …
- 32.1k
12
votes
Accepted
Interesting applications of max-flow and linear programming
Determining whether a sports team has been mathematically eliminated from qualifying for the playoffs is a cute application of max-flow min-cut:
http://www.cs.princeton.edu/courses/archive/spr03/cs2 …
11
votes
Accepted
Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?
Yes. This result is contained in my PhD thesis, which is available here (see Theorem 1.1.10). We prove that for any finite abelian group $\Gamma$ and fixed $\Gamma$-labeled graph $H$, there is a pol …
- 32.1k
11
votes
Accepted
Minimum number of edges to remove to have low degree
If you also insist that the bounded-degree subgraph is connected, then your problem is NP-Hard, since it includes the Longest Path problem when $k=2$.
On the other hand, without the connectivity cons …
- 32.1k
11
votes
Detection of Redundant Constraints
This can be done via linear programming. Consider a set of linear inequalities $Ax \leq b$, together with an additional inequality $c^Tx \leq d$. We wish to know if the constraint $c^Tx \leq d$ is r …
- 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
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
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of di …
- 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
7
votes
Accepted
Algorithm for the shortest path through all the points of a 2D cloud
If you only care about the length of the path between the first and last bus stops, then it looks like you are trying to solve the shortest Hamiltonian path problem (HPP). This is related to the more …
- 32.1k
6
votes
Finding a cycle of fixed length
If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed l …
- 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
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
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 …
- 32.1k