Abstract: This paper presents a service-oriented platform for development and execution of distributed applications based on contracting stationary and migrating services. Services are seen as active objects build on top of a middleware using CORBA and added features. Customized services add to the middleware the ability to handle transparently application start-up and distribution according to load-balancing and inverse caching application demand. Services can be considered of any kind ranging from scientific specialized processing to data archiving juke-boxes. An application on system management in scientific experimental environment is driving the work on some aspects of the architecture and the management.
Summary: Given a finite set of points on the plane, a planar triangulation is defined as a maximal set of line segments connecting these points, such that two of these segments do not intersect, except at the ends. We call the minimal cost triangulation the planar triangulation whose total sum of the lengths of its line segments is minimal among all the planar triangulations of the set of points in question.
There is no known polynomial algorithm that solves the problem of determining the minimum cost triangulation of a set of points in the general case, however, it is also not proven to be an NP-difficult problem.
In this article we are interested in the exact resolution of this problem. Our approach is based on whole programming techniques, in particular we evaluate two different formulations for the problem.
The first formulation is based on an equivalence between the minimum cost triangulation problem and a restricted version of the independent set problem in a graph. In addition to the inequalities obtained by observing this equivalence, we show how to strengthen the formulation through certain geometric properties of the problem.
We evaluate yet another formulation based mainly on the work presented by Loera et. al em The Polytope of All Triangulations of a Point Configuration, 12th European Workshop on Computational Geometry, 1996. Finally, we report our computational experiments.
Abstract: This paper presents part of the ongoing efforts at IC-UNICAMP to apply heuristic algorithms to vectorial georeferenced data in order to help decision support in urban planning. The results reported are original in the sense that they combine recent research in both combinatorial algorithm development and geographic databases, using them in the solution of a practical problem. A first prototype, described in the paper, has already been developed and tested against real data on the city of Campinas, to support planning activities for the S ao Paulo State Post Office System, Brazil.
Abstract: We present a model of office work and workflow systems that we call workcase centric, based on the view that office work is a collaborative construction of a case artifact. This model allows for the uniform treatment of cases for which the organization has no predefined procedure, of exceptional cases where the standard procedure must be modified, and of standard cases.
Abstract: This paper presents a temporal extension to the parsimonious covering theory (PCT), so instead of associating to each disorder a set of manifestation as it is done in PCT, one associates to each disorder a temporal graph that contains information about duration and elapsed time between the beginning of the manifestations. The definitions of solutions for temporal diagnostic problems are presented as well as algorithms that compute this solution. We also include some limited form of probabilistic information into the model in order to study how categorical rejection, the elimination of explanations that contain a disease for which a necessary manifestation is not present, interacts with temporal information. An application in a medical domain is presented and discussed.
Summary: This work shows that using `` A-Teams '' (Asynchronous Times) we can combine algorithms like Springs, Baricentro and random heuristics, in a simple and flexible way, so that they cooperate synergistically allowing graph design with two characteristics aesthetic problems, the corresponding problems of which are conflicting and NP-difficult.
Summary: We describe the approaches passive e active used for teaching algorithms and data structures with graphic animation resources. We introduce a new approach constructive and we describe the Astral environment designed to explore its benefits. In this approach, in addition to the student having access to sample applications provided with graphical animations that illustrate the operation of algorithms, he also makes his own animations during the process of implementing the structure and algorithms in a simplified way but with remarkable graphic visualization and appreciably positive results. in learning. The experience of using this environment has shown great advantages in teaching undergraduate courses in the field of computing.
Abstract: Some algorithms have been proposed to the problem of thinning 3D binary images. These algorithms use homotopic removal of points to achieve an skeleton whose structure preserves the topology of the original image. This work deals with technics for the optimization of such algorithms. Briefly, we present two methods that avoid unnecessary topology checking of the image points, leading to less time consuming sequential thinning.
Abstract: The traffic in the future Broadband Integrated Digital Networks is highly correlated and neglecting these correlations leads to a dramatic underestimation of performance. Being able to accurately estimate end-to-end performance is of paramount importance for traffic control. The purpose of this paper is to introduce a procedure for modeling the output process of a finite discrete time queue with selective discard mechanism loaded with a selected Discrete-time Batch Markovian Arrival Process (D-BMAP [H, L]) in which the priority level of a cell depends on the priority level of other cells in the flow. We show through numerical examples that his procedure is reasonably accurate. Moreover, we introduce a framework for the analysis of queuing networks with prioritized Markov Modulated flows.
Abstract: Video services is both a major business driver and a bandwidth consumer for the future broadband integrated network. Understanding different video services requirements is of paramount importance for network design. In this paper, we study Distributed Home Theater, a video service which allows distributed users to debate a film. We investigate the interplay between bandwidth reduction and program replication techniques. We evaluate the impact of user distribution, network topology and number of users per session on this interplay. Moreover, we state a bandwidth minimization principle which can be used in admission control policies.
Abstract: This paper presents a CPU designed for educational applications to be used in the Computer Architecture Laboratories, at IC / UNICAMP. The CPU will be used as a basic platform in order to introduce to the students novel design concepts such as VHDL, Logic Synthesis and FPGAs as well as a means to explore computer architecture characteristics and functionality. The paper also presents a few experiment possibilities, where the students incorporate new functions to the basic CPU using advanced techniques. The experiments complexity, the required design changes and their effects on the FPGA programming are also discussed.
Abstract: We present experimental results for four bipartite matching algorithms on 11 classes of graphs. The algorithms are depth-first search (DFS), breadth-first search (BFS), the push-relabel algorithm, and the algorithm by Alt, Blum, Mehlhorn, and Paul (ABMP). DFS was thought to be a good choice for bipartite matching but our results show that, depending on the input graph, it can have very poor performance. BFS on the other hand has generally very good performance. The results also show that the ABMP and push-relabel implementations are similar in performance, but ABMP was faster in most cases. We did not find a clear-cut advantage of ABMP over BFS or vice versa, but both the ABMP and push-relabel implementations have generally smaller growth rates than BFS, and should thus be preferred if very large problems are to be solved. For small problems BFS is the best choice. We also present experimental results from a parallel implementation of the push-relabel algorithm, showing that it can be up to three times faster than its sequential implementation, on a shared-memory multiprocessor using up to 12 processors.
Abstract: Statistical multiplexing was adopted in the ATM standard due to its potential for effective use of bandwidth. Coping with diverse Quality-of-Service requirements and with the variable-bit rate nature of multimedia applications makes traffic control a challenging task. In this paper, we show the advantages of adopting multi-level policing mechanism for ATM traffic control and compare different multi-level mechanisms based on the Leaky Bucket, on the Sliding Window and on the Jumping Window mechanism.
Summary: A comparability graph admits several transitive orientations. Each of them determines a source set for the graph. In this article we propose an algorithm that finds a transitive orientation that maximizes the source set of a comparability graph.
Abstract: Recently, much research effort has been employed in the area of Geographic Information Systems due to the vast potential for applications of this technology. Simultaneously, user interface subsystems of software products have received attention since the interface has marked influence in software acceptance. This paper presents an overview of research done in the intersection of these areas. The main approaches and the current problems of user interfaces for Geographical Information Systems are discussed and analyzed. This study concludes with open problems and new research directions for future work in this area.
Summary: This report presents a comparative study of methods for evaluating human-computer interfaces. The purpose of this study is to verify the applicability of these methods, comparing parameters such as the profile of the evaluators, the involvement of users and developers, time and material restrictions, scope of evaluation, steps and duration of the evaluation, adaptation to specific types of problems of usability, and others. With this study we intend to provide a comparative and classificatory view of assessment methods to assist assessment organizers in choosing methods and planning a better assessment approach.
Abstract: We consider the following question: can split graphs with odd maximum degree be edge-colored with maximum degree colors? We show that any odd maximum degree split graph can be transformed into a special split graph. For this special split graph, we were able to solve the question, in case the graph has a quasi-universal vertex.
Summary: In this work we address some problems related to the development of an electronic nautical chart system, through an approach of its basic functions and the associated data structures. With the use of printed nautical charts as the primary source of data, we present a sequence of operations to be performed during the phases of digitization, pre-processing and image processing. Representation schemes are also analyzed, considering the particular characteristics of these images and the operations to be performed on them.
Abstract: A two-dimensional cellular complex is a partition of a surface into a finite number of elements - faces (open disks), edges (open arcs), and vertices (points). The topology of a cellular complex consists of the abstract incidence and adjacency relations among its elements.
Here we describe a program that, given only the topology of a cellular complex, computes a geometric realization of the same - that is, a specific partition of a specific surface in three-space - guided by various aesthetic and presentational criteria.
Summary: The human-computer interface is one of the most important components of an interactive system. A large part of the current proposals for computer science courses curricular grids do not adequately address the various issues pertinent to this topic. This text proposes the organization of an undergraduate course of this nature. The construction of the interface of an interactive system is presented and exemplifies the type of practical work that can be done by students.
Instituto de Computação :: State University of Campinas
PO Box 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas / SP - Brazil • Phone: [19] 3521-5838 |