Tagged Questions

Questions relating to implementations of algorithms

118 views

Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...
254 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, ...
276 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 ...
57 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 ...
229 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?
213 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 ...
213 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 ...
118 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) ...
196 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 engine,...
1k 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 ...
314 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 ...
782 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 it'...
296 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 ...
171 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? ...
490 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 ...
203 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? ...
306 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 ...
237 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 ...
2k 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 ...
611 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? ...
10k 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 ...
544 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 ...
1k 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 ...