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.
0
votes
Accepted
Maximizing number of factors contributing in the sum of sorted array bounded by a value
It seems that $O(n \log (n))$ is possible. Just process the array from left to right as follows. At time $t$ we store both $\mathbf{X}_t$ and $\mathbf{Y}_t$ which are respectively the best valid seq …
- 32.1k
2
votes
Area of an irregular, n-sided, non-intersecting (edges) polygon algorithm
Given a set of $n$ points in the plane, the problem of finding a minimum area convex $k$-gon among the points was considered by Eppstein, Overmars, Rote, and Woeginger in this paper. They give an alg …
- 32.1k
4
votes
Accepted
Graph algorithm to find all subgraphs that connect N arbitrary vertices
It looks like the paper
Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals
by Costa Dourado, de Oliveira, and Protti is what you want (available from …
- 32.1k
0
votes
Checking whether a set family forms a matroid.
Here's a probabilistic approach.
First check if your set family $\mathcal{I}$ is closed under taking subsets. If not, then it is not a matroid. Next assign a 'random' weight function $w: S \to \m …
- 32.1k
2
votes
Breaking frustrated loops in list coloring problem
It sounds like you are asking if the Erdős–Pósa property holds for frustrated cycles. That is, does there exists a function $f: \mathbb{N} \to \mathbb{N}$,
such that every graph (with lists) either …
- 32.1k
2
votes
Accepted
Testing connectivity when deleting an edge
I would say yes. If the connectivity between $x$ and $y$ has decreased, then obviously the connectivity of $G$ has decreased. On the other hand, if $G - e$ is not 3-connected, then there are a pair …
- 32.1k
3
votes
partitioning a number into two sets based on sum of digits
This isn't really an answer, but just a short proof that there are indeed a finite number of minimal partitions. See ARupinski's answer for a definition of minimal partition.
Lemma. There are a fi …
- 32.1k
1
vote
How to do a clockwise ordering of a planar graph in order to define its faces?
On the other hand, if you only want to find one planar embedding, then there are many planarity testing algorithms that actually output a planar embedding (if it exists). …
- 32.1k
1
vote
Accepted
how to reduce 3-colorable graph to this?
This problem is indeed NP-complete and was in fact one of Karp's 21 NP-complete problems. Googling exact cover will lead to enlightenment.
- 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
2
votes
What are the most fundamental classes of mathematical algorithms?
What about algorithms coming from graph theory? This seems to be a rich source with lots of real world applications too. … To mention just a few
Minimum weight spanning tree
Maximum weight matchings
Colouring algorithms
Minor-testing …
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
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
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
4
votes
Accepted
Minimal Support Solutions of a Linear System (Dissertation)
The problem of determining a minimum support solution of a linear system is indeed NP-hard. Here is a reduction that works over the binary field $\mathbb{F}_2$. Given a graph $G$, an odd dominating …
- 32.1k