archive-lt.com » LT » T » THERAN.LT Total: 41 Choose link from "Titles, links and description words view": Or switch to
"Titles and links view". |

- Characterizing sparse graphs by map decompositions

Ileana Streinu and Louis Theran Journal Journal of Combinatorial Mathematics and Combinatorial Computing 62 2007 Full text arXiv A map is a graph that admits an orientation of its edges so that each vertex has out degree exactly 1 We characterize graphs which admit a decomposition into edge disjoint maps after 1 the addition of any edges 2 the addition of some edges These graphs are identified with classes of

Original URL path: http://theran.lt/papers/j002-maps.html (2016-04-26)

Open archived version from archive - Graded sparse graphs and matroids

of Universal Computer Science 13 11 1671 1679 2007 Full text arXiv DOI Sparse graphs and their associated matroids play an important role in rigidity theory where they capture the combinatorics of generically rigid structures We define a new family called graded sparse graphs arising from generically pinned completely immobilized bar and joint frameworks and prove that they also form matroids We address five problems on graded sparse graphs Decision

Original URL path: http://theran.lt/papers/j001-graded.html (2016-04-26)

Open archived version from archive - Delaunay triangulations with disconnected realization spaces

realization spaces of Delaunay triangulations and show that they can be arbitrarily complicated and in particular disconnected Our smallest example consists of two configurations of labeled points in whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the triangulation In general we prove that the realization space of a Delaunay triangulation in can have connected components Our proof

Original URL path: http://theran.lt/papers/c012-disconnected.html (2016-04-26)

Open archived version from archive - Detecting dependencies in geometric constraint systems

Computer Aided Design software Automated approaches for detecting dependencies in a design are critical for developing robust solvers and provid ing informative user feedback and we provide algorithms that recognize two types of dependencies First we give a pebble game algorithm for detecting generic dependencies Then we focus on identifying the special positions of a design in which generically independent constraints become dependent We present combinatorial algorithms for identifying subgraphs

Original URL path: http://theran.lt/papers/c011-special.html (2016-04-26)

Open archived version from archive - Generic rigidity with forced symmetry and sparse colored graphs

2014 Full text arXiv DOI We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry giving a uniform treatment to the topic We also give new combinatorial characterizations of minimally rigid periodic frameworks with

Original URL path: http://theran.lt/papers/c010-colored.html (2016-04-26)

Open archived version from archive - Error-Minimizing Estimates and Universal Entry-Wise Error Bounds for Low-Rank Matrix Completion

13 2013 Full text arXiv URL We propose a general framework for reconstructing and denoising single entries of incomplete and noisy entries We describe effective algorithms for deciding if and entry can be reconstructed and if so for reconstructing and denoising it and a priori bounds on the error of each entry individually In the noiseless case our algorithm is exact For rank one matrices the new algorithm is fast

Original URL path: http://theran.lt/papers/c009-rank1.html (2016-04-26)

Open archived version from archive - Rigid components in fixed-lattice and cone frameworks

Geometry CCCG 11 2011 Full text arXiv URL We study the fundamental algorithmic rigidity problems for generic frameworks periodic with respect to a fixed lattice or a finite order rotation in the plane For fixed lattice frameworks we give an algorithm for deciding generic rigidity and an algorithm for computing rigid components If the order of rotation is part of the input we give an algorithm for deciding rigidity in

Original URL path: http://theran.lt/papers/c008-symmetriccomps.html (2016-04-26)

Open archived version from archive - Searching in tree-like partial orders

Algorithms and Data Structures WADS 11 2011 Full text arXiv DOI We give the first data structure for the problem of maintaining a dynamic set of n elements drawn from a partially ordered universe described by a tree We define the Line Leaf Tree a linear sized data structure that supports the operations insert delete test membership and predecessor The performance of our data structure is within an factor of

Original URL path: http://theran.lt/papers/c007-partial.html (2016-04-26)

Open archived version from archive