Questions relating to implementations of algorithms

learn more… | top users | synonyms

4
votes
1answer
110 views

Implementation of partition trees?

Have partition trees ever been implemented? Here, I'm talking about the partition trees from computational geometry. The earliest (near-)optimal versions of which were due to Matousek and others, ...
7
votes
2answers
156 views

Implementation of surreal numbers for games

There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they ...
1
vote
0answers
48 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
17
votes
1answer
213 views

A good Library for testing whether a minors exists in a graph?

I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
-1
votes
1answer
108 views

Implementation of Kallmann's Dynamic Constrained Delaunay Triangulation algorithm

Does anyone know of any open source implementation (preferably in java) of Kallmann's DCDT algorithm? If there's another DCDT algorithm that has been implemented, that may work as well. I wasn't sure ...
4
votes
1answer
196 views

Implementations of Undirected Disjoint Paths

I'm looking into the Undirected Vertex Disjoint Paths problem: Given a list of tuples of vertices (s_i, t_i) Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects ...
0
votes
1answer
100 views

How would you define a set of 'fundamental operations' over an object? [closed]

I'm writing an implementation for a common array structure. As you would find already familiar, an array is an ordered data structure that you can transform with different (hopefully self-explained) ...
4
votes
1answer
158 views

Are there any implementations for zero-knowledge proofs of NP-complete problems?

It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search ...
5
votes
1answer
578 views

Implementation that solves minimum set cover

Does anyone know of any tools that solve the approximate minimum set cover problem? I know of the greedy algorithm (which is straightforward to implement myself), but I've also been reading about ...
9
votes
0answers
255 views

Implementation of Wilf-Zeilberger and related methods

The book A=B by Petkovsek, Wilf and Zeilberger describes algorithms to compute different sums of binomials. AFAIK, these algorithms are still being improved by different authors. Do you know where ...
1
vote
1answer
358 views

Any existing Reeds-Shepp implementations?

Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car? I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think ...
0
votes
0answers
223 views

Implementation of a Logical Hierarchical Hidden Markov Model

Is anyone aware of any implementations of algorithms for learning and/or processing a Logical Hierarchical Hidden Markov Model, as described in this paper? I've found dozens of papers about Logical ...
4
votes
0answers
166 views

Implementable algorithm for Voronoi regions with obstacles

I'm looking for an algorithm that computes the Voronoi regions of a set of points contained in a polygonal region with obstacles. What would be the most simple, straightforward way to implement this? ...
12
votes
3answers
415 views

Implemented code to compute pathwidth (= Node search number, vertex separation number, interval thickness)

I am looking for an implementation of an algorithm to compute the pathwidth of a graph. It is well known that computing the pathwidth is equivalent to computing the node searching number, vertex ...
1
vote
1answer
197 views

Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
3
votes
1answer
288 views

Are there good implementations for easy subclasses of NP-hard graph problems

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
2
votes
1answer
225 views

Explain 0-extension algorithm

I'm trying to implement an approximation algorithm for the 0-extension problem I found the following paper: Approximation Algorithms for the 0-extension problem by Gruia Calinescu, Howard ...
10
votes
5answers
1k views

Best book on Simplex Method implementation?

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
2
votes
1answer
537 views

Powerful Algorithms that are just too Hard to Implement— How to be sure They are Right?

I am referring to the question here: powerful algorithms too complex to implement. If an algorithm is powerful, but too complex to implement, how can you be sure that the algorithm is correct? ...
45
votes
8answers
8k views

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
19
votes
4answers
476 views

Is there current research into the implemention of Randomness Extractors?

Has there been research into implementing randomness extractor constructions? It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
11
votes
2answers
798 views

Fast sparse boolean matrix product with possible preprocessing

What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)? Actually, I have the advantage that ...