U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Search Publications by:

Search Title, Abstract, Conference, Citation, Keyword or Author
Displaying 26 - 50 of 52

Measuring the Effectiveness of the s-Metric to Produce Better Network Models

December 7, 2008
Author(s)
Isabel M. Beichl, Brian D. Cloteaux
Recent research has shown that while many complex networks follow a power-law distribution for their vertex degrees, it is not sufficient to model these networks based only on their degree distribution. In order to better distinguish between these networks

Generating Network Models Using the S-Metric

July 14, 2008
Author(s)
Isabel M. Beichl, Brian D. Cloteaux
The ability to create random models of real networks is useful for understanding the interactions of the networks. Several researchers have proposed modeling of complex networks using the degree distribution, the most popular being a power-law distribution

A Quantum Algorithm Detecting Concentrated Maps

November 1, 2007
Author(s)
Isabel M. Beichl, Stephen Bullock, David Song
We consider an arbitrary mapping for , some number of quantum bits. Using calls to a classical oracle evaluating and an classical bit data store, it is possible to determine whether is one-to-one. For some radian angle , we say is -concentrated iff for

The Other Monte Carlo Method

March 1, 2006
Author(s)
Isabel M. Beichl, Francis Sullivan
This is a general article on a Monte Carlo method different from the traditional Metropolis algorithm. Sampling is done according to a non-uniform probability distribution that is generated as the choice is being made.

Applications of Sinkhorn Balancingto Counting Problems

July 1, 2004
Author(s)
Isabel M. Beichl, F Sullivan
We describe a gneral Monte Carlo technique based on work of Knuth for estimating the size of trees in backtrack algorithms. This method, based on importance sampling, is used to estimate the number of partial and complete matchings in a bipartite graph

Applications of Sinkhorn Balancing: The Monomer-Dimer Problem

January 30, 2004
Author(s)
Isabel M. Beichl, Francis Sullivan
We describe a general Monte Carlo technique based on work of Knuth for estimating the size of trees in backtrack algorithms. This method, based on importance sampling, is used to estimate the number of partial and complete matchings in a bipartite graph

Estimating the Work in Integer Partitioning

January 31, 2003
Author(s)
April Andreas, Isabel M. Beichl
For a given set of numbers, the integer partitioning problem is to divide the numbers into two groups, so that the sums of the numbers in each group differ by the smallest amount possible. In a balanced perfect partition, the sums differ by only zero or

Dealing with Degeneracy in Triangulation

November 1, 2002
Author(s)
Francis Sullivan, Isabel M. Beichl
This is a tutorial article on a quick method for dealing with degeneracy in geometric computations with specific reference to triangulation. The type degeneracy targeted by this article that of four or more points on a circle and five or more points on a

It's Bound to Be Right

April 1, 2002
Author(s)
Isabel M. Beichl, F Sullivan
This is a tutorial article on a Monte Carlo method for eliminating double counting in massive data sets. It has also been used to classify images.

Approximating the Number of Monomer-Dimer Coverings in Periodic Lattices

July 1, 2001
Author(s)
Isabel M. Beichl, Dianne M. O'Leary, F Sullivan
Our starting point is an algorithm of Kenyon, Randall, and Sinclair, which built upon the ideas of Jerrum and Sinclair, giving an approximation to crucial parameters of the monomer-dimer covering problem in polynomial time. We make two key improvements to

In Order to Form a More Perfect UNION

April 1, 2001
Author(s)
Isabel M. Beichl, F Sullivan
In this computing prescription we present an algorithm for finding a minimum spanning tree figure 1 shows a typical application of this MST algorithm. Here we have 11 data points in a plane and would like to find some structure among them. Suppose we draw

Determining the Determinant

September 1, 2000
Author(s)
Isabel M. Beichl, F Sullivan
In this Installment, we describe the bareiss method for finding the determinant of an integer matrix where all the arithmetic is done in integer mode. Of course, it will also work for any kind of matrix even if not using integers, but there are better ways

A=B?

May 1, 2000
Author(s)
Isabel M. Beichl, F Sullivan
In this prescription we'll describe one technique for working with extremely large integers having perhaps thousands of digits, using only standard hardware and software. This technique uses modular arithmetic in a way that lets us recover the actual

The Metropolis Algorithm

January 1, 2000
Author(s)
Isabel M. Beichl, F Sullivan
This is a survey of the Metropolis Algorithm for the IEEE special issue on the 10 most important algorithms of the century.

Pay Me Now or Pay Me Later

August 1, 1999
Author(s)
Isabel M. Beichl, F Sullivan
This is a tutorial article on the alias method which we use to sample from the Poisson distribution quickly.

The Importance of Importance Sampling

April 1, 1999
Author(s)
Isabel M. Beichl, F Sullivan
This is a tutorial article on Monte Carlo technique of importance sampling that has been under-appreciated. We recently used it with great success and so we share our insights with our readers. Importance sampling is a form of Monte Carlo sampling designed

Interleave in Peace, or Interleave in Pieces

September 1, 1998
Author(s)
Isabel M. Beichl, F Sullivan
Bit interleaving is a technique that sometimes can collapse a problem of high-dimensional data to one of lower dimensional data. Our favorite use is going from two or three dimensions to one dimension. Of course, you lose something in this process because

Make Me a Match

October 1, 1997
Author(s)
Isabel M. Beichl, F Sullivan
This is a tutorial article on the Hopcroft-Karp algorithm for finding a maximal matching in an undirected graph.