All Outputs (82)

Finding paths between 3-colorings (2011)
Journal Article

Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are pro... Read More about Finding paths between 3-colorings.

Simulating Human Cardiac Electrophysiology on Clinical Time-Scales (2011)
Journal Article

In this study, the feasibility of conducting in silico experiments in near-realtime with anatomically realistic, biophysically detailed models of human cardiac electrophysiology is demonstrated using a current national high-performance computing faci... Read More about Simulating Human Cardiac Electrophysiology on Clinical Time-Scales.

Multidepth, multiparticle tracking for active microrheology using a smart camera (2011)
Journal Article

The quantitative measurement of particle motion in optical tweezers is an important tool in the study of microrheology and can be used in a variety of scientific and industrial applications. Active microheology, in which the response of optically tra... Read More about Multidepth, multiparticle tracking for active microrheology using a smart camera.

A Matroid Framework for Noncoherent Random Network Communications (2011)
Journal Article

Realizing Perceptive Virtual Reality Imaging Applications on Conventional PC Hardware (2011)
Journal Article

Adaptive optics for wide-field microscopy (2011)
Presentation / Conference Contribution

We report on recent developments in the use of adaptive optics (AO) in wide-field microscopy to remove both system and sample induced aberrations. We describe progress on using both a full AO system and image optimization techniques (wavefront sensor... Read More about Adaptive optics for wide-field microscopy.

Heart synchronization for SPIM microscopy of living zebra fish (2011)
Presentation / Conference Contribution

We describe work on producing a selective plane illumination microscope for cardiac imaging in zebra fish embryos. The system has a novel synchronization system for imaging oscillating structures (e.g. the heart) and will have adaptive optics for ima... Read More about Heart synchronization for SPIM microscopy of living zebra fish.

Conjugate-plane photometry: reducing scintillation in ground-based photometry (2011)
Journal Article

High-precision fast photometry from ground-based observatories is a challenge due to intensity fluctuations (scintillation) produced by the Earth's atmosphere. Here we describe a method to reduce the effects of scintillation by a combination of pupil... Read More about Conjugate-plane photometry: reducing scintillation in ground-based photometry.

Randomized Diffusion for Indivisible Loads (2011)
Presentation / Conference Contribution

We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tok... Read More about Randomized Diffusion for Indivisible Loads.

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (2011)
Book Chapter

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argume... Read More about Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width.

Satisfiability of acyclic and almost acyclic CNF formulas (II) (2011)
Presentation / Conference Contribution

In the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β-acyclic formul... Read More about Satisfiability of acyclic and almost acyclic CNF formulas (II).

On Finding Paths Passing through Specified Vertices (2011)
Report

We consider undirected finite graphs that have no loops and no multiple edges. A graph is denoted G = (VG, EG), where VG is the set of vertices and EG is the set of edges. A graph containment problem is to decide whether one graph can be modified int... Read More about On Finding Paths Passing through Specified Vertices.

An intersection model for multitolerance graphs: Efficient algorithms and hierarchy (2011)
Presentation / Conference Contribution

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in con ict. This class of graphs has attracted many research eorts, mainly due to its interesting structure and its numerous... Read More about An intersection model for multitolerance graphs: Efficient algorithms and hierarchy.

Contracting a chordal graph to a split graph or a tree (2011)
Presentation / Conference Contribution

The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input gr... Read More about Contracting a chordal graph to a split graph or a tree.

The computational complexity of Disconnected Cut and 2K2-Partition (2011)
Presentation / Conference Contribution

For a connected graph G = (V,E), a subset U ⊆ V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. Thi... Read More about The computational complexity of Disconnected Cut and 2K2-Partition.

List coloring in the absence of a linear forest (2011)
Presentation / Conference Contribution

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some g... Read More about List coloring in the absence of a linear forest.

The Recognition of Triangle Graphs (2011)
Presentation / Conference Contribution

Trapezoid graphs are the intersection graphs of trapezoids, where every trapezoid has a pair of opposite sides lying on two parallel lines L_{1} and L_{2} of the plane. Strictly between permutation and trapezoid graphs lie the simple-triangle graphs... Read More about The Recognition of Triangle Graphs.

Computing vertex-surjective homomorphisms to partially reflexive trees (2011)
Presentation / Conference Contribution

Coloring graphs without short cycles and long induced paths (2011)
Presentation / Conference Contribution

The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the ex... Read More about Coloring graphs without short cycles and long induced paths.

Augmented k-ary n-cubes (2011)
Journal Article

We define an interconnection network AQn,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmen... Read More about Augmented k-ary n-cubes.