Descripción: We propose a new data structure for manipulating graphs, called h-graph, which is particularly suited for designing dynamic algorithms. The structure itself is simple, consisting basically of a triple of elements, for each vertex of the graph. The overall size of all triples is O(n+m), for a graph with n vertices and m edges. We describe algorithms for performing the basic operations related to dynamic applications, as insertions and deletions of vertices or edges, and adjacency queries. The data structure employs a technique first described by Chiba and Nishizeki [Chiba, Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1) (1985) 210223], and relies on the arboricity of graphs. Using the proposed data structure, we describe several dynamic algorithms for solving problems as listing the cliques of a given size, recognizing diamond-free graphs, and finding simple, simplicial and dominated vertices. These algorithms are the first of their kind to be proposed in the literature. In fact, the dynamic algorithms for the above problems lead directly to new static algorithms, and using the data structure we also design new static algorithms for the problems of counting subgraphs of size 4, recognizing cop-win graphs and recognizing strongly chordal graphs. The complexities of all of the proposed static algorithms improve over the complexities of the so far existing algorithms, for graphs of low arboricity. In addition, for the problems of counting subgraphs of size 4 and recognizing diamond-free graphs, the improvement is general. © 2011 Elsevier B.V. All rights reserved.

Descripción: Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. © 2008 Elsevier B.V. All rights reserved.

Descripción: Fil:Flexer, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm. © 2007 Elsevier B.V. All rights reserved.

Descripción: We present a symbolic probabilistic algorithm to compute the isolated roots in Cn of sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a geometric resolution of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports. © 2010 Elsevier B.V. All rights reserved.

Descripción: Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: Given a reduced affine algebra A over a perfect field K, we present parallel algorithms to compute the normalization Ā of A. Our starting point is the algorithm of Greuel et al. (2010), which is an improvement of de Jong's algorithm (de Jong, 1998; Decker et al., 1999). First, we propose to stratify the singular locus Sing(A) in a way which is compatible with normalization, apply a local version of the normalization algorithm at each stratum, and find Ā by putting the local results together. Second, in the case where K=Q is the field of rationals, we propose modular versions of the global and local-to-global algorithms. We have implemented our algorithms in the computer algebra system Singular and compare their performance with that of the algorithm of Greuel et al. (2010). In the case where K=Q, we also discuss the use of modular computations of Gröbner bases, radicals, and primary decompositions. We point out that in most examples, the new algorithms outperform the algorithm of Greuel et al. (2010) by far, even if we do not run them in parallel. © 2012 Elsevier B.V.

Descripción: We consider a family of polynomial systems which arises in the analysis of the stationary solutions of a standard discretization of certain semi-linear second-order parabolic partial differential equations. We prove that this family is well-conditioned from the numeric point of view, and ill-conditioned from the symbolic point of view. We exhibit a polynomial-time numeric algorithm solving any member of this family, which significantly contrasts the exponential behavior of all known symbolic algorithms solving a generic instance of this family of systems. © 2005 Elsevier Inc. All rights reserved.

Descripción: Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information. © 2006 Elsevier B.V. All rights reserved.

Descripción: Text information in images and videos is frequently a key factor for information indexing and retrieval systems. However, text detection in images is a difficult task since it is often embedded in complex backgrounds. In this paper, we propose an accurate text detection and localization method in images based on stroke information and the Adaptive Run Lenght Smoothing Algorithm. Experimental results show that the proposed approach is accurate, has high recall and is robust to various text sizes, fonts, colors and languages. © 2011 Springer-Verlag.

Descripción: In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions. © 2010 Elsevier B.V. All rights reserved.

Descripción: This paper addresses a license plate detection and recognition (LPR) task on still images of trucks. The main contribution of our LPR system is the fusion of different segmentation algorithms used to improve the license plate detection. We also compare the performance of two kinds of classifiers for optical character recognition (OCR): one based on the a contrario framework using the shape contexts as features and the other based on a SVM classifier using the intensity pixel values as features. © 2010 Springer-Verlag.

Descripción: This work describes simple decompositions of the energy of molecular systems according to schemes that partition the three-dimensional space. The components of those decompositions depend on one and two atomic domains thus providing a meaningful chemical information about the nature of different bondings among the atoms which compose the system. Our algorithms can be applied at any level of theory (correlated or uncorrelated wave functions). The results reported here, obtained at the Hartree-Fock level in selected molecules, show a good agreement with the chemical picture of molecules and require a low computational cost in comparison with other previously reported decompositions.

Descripción: Fil:Braberman, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Descripción: We introduce the notion of a T-path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between T-paths and firable sequences of transitions. Let us consider a Petri net P=〈P,T,A,M0〉 and the set of places with a positive marking in M0, i.e., P0=p|M0(p)>0. If we regard the net as a directed graph, the existence of a simple path from any place in P0 to a transition t is, of course, a necessary condition for the potential firability of t. This is sufficient only if the net is a state machine, where |•t|=|t•|=1 for all t∈T. In this paper we show that the existence of a T-path from any subset of P0 to a transition t is a more restrictive condition and is, again, a necessary condition for the potential firability of t. But, in this case: (a) if P is a conflict-free Petri net, this is also a sufficient condition, (b) if P is a general Petri net, t is potentially firable by increasing the number of tokens in P0. For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of coverable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i.e., O(|P|+|T|+|A|), for a net P=〈P,T,A,M0〉. Previous results for this class of networks are given by Howell et al. (1987) [20], providing algorithms for solving problems in conflict-free nets in O(|P|×|T|) time and space. Given a Petri net and a marking M, the well-known coverability problem consists in finding a reachable marking M′ such that M′ ...ver más