1,721,312 research outputs found
Proximity drawings: three dimensions are better than two
No full textWe consider weak Gabriel drawings of unbounded degree trees in the three-dimensional space. We assume a minimum distance between any two vertices. Under the same assumption, there exists an exponential area lower bound for general graphs. Moreover, all previously known algorithms to construct (weak) proximity drawings of trees, generally produce exponential area layouts, even when we restrict ourselves to binary trees. In this paper we describe a linear-time polynomial-volume algorithm that constructs a strictly-upward weak Gabriel drawing of any rooted tree with O(log n)-bit requirement. As a special case we describe a Gabriel drawing algorithm for binary trees which produces integer coordinates and n 3-area representations. Finally, we show that an infinite class of graphs requiring exponential area, admits linear-volume Gabriel drawings. The latter result can also be extended to β-drawings, for any 1 < β < 2, and relative neighborhood drawings
Linear Area Upward Drawings of AVL Trees
No full textAbstractWe prove that any AVL tree admits a linear-area straight-line strictly-upward planar grid drawing, that is, a drawing in which (a) each edge is mapped into a single straight-line segment, (b) each node is placed below its parent, (c) no two edges intersect, and (d) each node is mapped into a point with integer coordinates
Sistema Informativo di supporto alle decisioni per la valutazione dell’ impatto sul territorio interessato dall’ erogazione dei fondi previsti dal T.U. 309/90 (SSDD-Droga): Il GIS e i dati dei Sert
No full textOn-line algorithms for the channel assignment problem in cellular networks
Full text linkWe consider the on-line channel assignment problem in the case of cellular networks and we formalize this problem as an on-line load balancing problem for temporary tasks with restricted assignment. For the latter problem, we provide a general solution (denoted as the cluster algorithm) and we characterize its competitive ratio in terms of the combinatorial properties of the graph representing the network. We then compare the cluster algorithm with the greedy one when applied to the channel assignment problem: it turns out that the competitive ratio of the cluster algorithm is strictly better than the competitive ratio of the greedy algorithm. The cluster method is general enough to be applied to other on-line load balancing problems and, for some topologies, it can be proved to be optimal. (C) 2003 Elsevier B.V. All rights reserved
On-line algorithms for the channel assignment problem in cellular networks
No full textWe consider the on-line channel assignment problem in the case of cellular networks and we formalise this problem as an on-line load balancing problem of temporary tasks with restricted assignment. For the latter problem, we provide a general solution (denoted as the cluster algorithm) and we characterise its competitive ratio in terms of the combinatorial properties of the graph representing the network. We then compare the cluster algorithm with the greedy one when applied to the channel assignment problem: It turns out that the competitive ratio of the cluster algorithm is strictly better than the competitive ratio of the greedy algorithm. The cluster method is general enough to be applied to other on-line load balancing problems and, for some topologies, it can be proved to be optimal
An Equivalent Version of the Caccetta-Haeggkvist Conjecture in an Online Load Balancing Problem
No full textNo truthful mechanism can be better than n approximate for two natural problems
No full textThis work gives the first natural non-utilitarian problems for which the trivial n approxima-tion via VCG mechanisms is the best possible. That is, no truthful mechanism can be better than n approximate, where n is the number of agents. The problems we study are the min-max variant of the shortest path and the (directed) minimum spanning tree mechanism design problems. In these procurement auctions, agents own the edges of a network, and the corresponding edge costs are private. Instead of the total weight of the subnetwork, in the min-max variant we aim to minimize the maximum agent cost
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
