186,918 research outputs found
Proximity drawings in polynomial area and volume
No full textWe introduce a novel technique for drawing proximity graphs in polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first algorithms to construct (a) polynomial area weak Gabriel drawings of ternary trees, (b) polynomial area weak β-proximity drawing of binary trees for any 0⩽β<∞, and (c) polynomial volume weak Gabriel drawings of unbounded degree trees. Notice that, in general, the above graphs do not admit a strong proximity drawing. Finally, we give evidence of the effectiveness of our technique by showing that a class of graph requiring exponential area even for weak Gabriel drawings, admits a linear-volume strong β-proximity drawing and a relative neighborhood drawing. All described algorithms run in linear time
Representing graphs implicitly using almost optimal space
No full textHow to represent a graph in memory is a fundamental data-structuring problem. In the usual representations, a graph is stored by representing explicitly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and reveal nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any two given vertices can be tested in constant time. The labeling scheme assigns to each vertex x a O(delta (x) log(2) n) bit label, where n is the number of vertices and delta (x) is x's degree. The adjacency test can be performed in seven steps and the scheme can be computed in polynomial time. The proposed graph encoding positively demonstrates its superiority over the usual representations, i.e. adjacency matrix and adjacency list representations, which require O(n log n) bit label per vertex and constant time adjacency test, and O(delta (x)log n) bit label per vertex and O(log delta (x)) steps to test adjacency, respectively. Additionally, the labeling scheme is implicit, that is: no pointers are used. (C) 2001 Elsevier Science B.V. All rights reserved
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
Efficient data structure for lattice operations
No full textIn this paper, we consider the representation and management of an element set on which a lattice partial order relation is defined. In particular, let n be the element set size. We present an O(n root n)-space implicit data structure for performing the following set of basic operations: 1. Test the presence of an order relation between two given elements, in constant time. 2. Find a path between two elements whenever one exists, in O(l) steps, where l is the path length. 3. Compute the successors and/or predecessors set of a given element, in O(h) steps, where h is the size of the returned set. 4. Given two elements, find all elements between them, in time O(k log d), where k is the size of the returned set and d is the maximum in-degree or out-degree in the transitive reduction of the order relation. 5. Given two elements, find the least common ancestor and/or the greatest common successor in O(root n)-time. 6. Given k elements, find the least common ancestor and/or the greatest common successor in O(root n + k log n)time. (Unless stated otherwise, all logarithms are to the base 2.) The preprocessing time is O(n(2)). Focusing on the first operation, representing the building-box for all the others, we derive an overall O(n root n)-space x time bound which beats the order n(2) bottleneck representing the present complexity for this problem. Moreover, we will show that the complexity bounds for the first three operations are optimal with respect to the worst case. Additionally, a stronger result can be derived. In particular, it is possible to represent a lattice in space O(n root t), where t is the minimum number of disjoint chains which partition the element set
Proximity Drawings in Polynomial Area and Volume
No full textWe introduce a novel technique for drawing proximity graphs in
polynomial area and volume. Previously known algorithms produce representations whose size increases exponentially with the size of the graph. This holds even when we restrict ourselves to binary trees. Our method is quite general and yields the first
algorithms to construct polynomial area weak Gabriel
drawings of ternary trees, polynomial area weak
\beta-proximity drawing of binary trees for any 0 =< \beta
< \infty, and polynomial volume weak Gabriel drawings of
unbounded degree trees. Notice that, in general, the above
graphs do not admit a strong proximity drawing. Finally, we
give evidence of the effectiveness of our technique by showing
that a class of graph requiring exponential area even for
weak Gabriel drawings, admits a linear volume strong
\beta-proximity drawing and a relative neighborhood
drawing. All the algorithms described run in linear time
Teoria dei giochi
No full textLa Teoria dei Giochi è la scienza matematica che analizza situa zioni di conflitto e ne ricerca soluzioni competitive e cooperative. Studia le decisioni individuali in situazioni in cui vi sono interazioni tra diversi soggetti. È una disciplina relativamente nuova, formalizzata all’inizio del secolo scorso, e recentemente venuta all’attenzione del grande pubblico grazie anche alla pubblicazione di diversi saggi divulgativi e non, ma soprattutto per la realizzazione di film e citazioni in telefilm ad ampia diffusione che ne hanno descritto, seppur in maniera informale e romanzata, alcuni aspetti più caratteristici e intriganti.
Gli strumenti della Teoria dei Giochi permettono di analizzare le eventuali situazioni di equilibrio e la loro bontà rispetto a una soluzione ottima dal punto di vista sociale. Le sue applicazioni e interazioni sono molteplici: dall’economia e finanza, alle strategie militari; dalla politica alla sociologia, dalla psicologia all’informatica, dalla biologia allo sport.
In questo breve lavoro si intende descriverne i princìpi fondamentali e fornirne alcuni esempi tra i più significativi, senza pretendere di entrare nei dettagli matematici sottostanti che, pur di per sé decisamente interessanti, sono al di là dello scopo di questo articolo.
Per concludere, si analizzerà un altro aspetto della Teoria dei Giochi riguardante il Mechanism Design che si occupa di progettare meccanismi che conducano i giocatori di un gioco a fare delle scelte che siano in accordo con il concetto di soluzione prefissata. In questo contesto, mostreremo come qualunque sistema di voto non sia equo e possa essere manipolato, essendo il solo sistema non manipolabile la dittatura.
o il solo sistema non manipolabile la dittatura
A data structure for lattice representation
No full textAbstractIn this paper, we present an implicit data structure for the representation of a partial lattice L = (s, N), which allows to test the partial order relation among two given elements in constant time. The data structure proposed has an overall O(n√n)-space complexity, where n is the size of ground set N, which we will prove to be optimal in the worst case. Hence, we derive an overall O(n√n) -space∗time bound for the relation testing problem thus beating the O(n2) bottle-neck representing the present complexity.The overall pre-processing time is O(n2)
Compact implicit representation of graphs (extended abstract)
No full textHow to represent a graph in memory is a fundamental data structuring problem. In the usual representations, a graph is stored by representing explicitly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and betray nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any two given vertices can be tested in constant time. The labeling schema assigns to each vertex a of a general graph a O(delta(x) log(3) n) bit label, where n is the number of vertices and delta(x) is x's degree. The adjacency test can be performed in 5 steps and the schema can be computed in polynomial time. This representation strictly contrasts with usual representations, i.e. adjacency matrix and adjacency list representations, which require O(n log n) bit label per vertex and constant time adjacency test, and O(delta(x) log n) bit label per vertex and O(log delta(x)) steps to test adjacency, respectively. Additionally, the labeling schema is implicit, that is: no pointers are used
Proximity Drawings: Three Dimensions Are Better than Two (Extended Abstract)
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(logn)-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 \beta -drawings, for any 1< \beta <2, and relative neighborhood drawings
On the approximability of the L(h, k)-labelling problem on bipartite graphs (Extended abstract)
No full textGiven an undirected graph G, an L(h, k)-labelling of G assigns colors to vertices from the integer set {0,.. lambda(h,k)}, such that any two vertices v(i) and v(j) receive colors c(v(i)) and c(v(j)) satisfying the following conditions: i) if v(i) and v(j) are adjacent then vertical bar c(v(i)) - c(v(j))vertical bar >= h; ii) if v(i) and v(j) are at distance two then vertical bar c(v(i)) - c(v(j))vertical bar >= k. The aim of the L(h, k)-labelling problem is to minimize lambda(h,k)- In this paper we study the approximability of the L(h,k)-labelling problem on bipartite graphs and extend the results to s-partite and general graphs. Indeed, the decision version of this problem is known to be DIP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the L(h,k)-labelling problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an L(h, k)-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by (4)/D-3(2), where, D is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension d, i.e. the maximum edge cardinality, with performance ratio d. Furthermore, we consider a different approximation technique based on the reduction of the L(h, k)-labelling problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by min(h, 2k)root n + o(k root n), assuming h >= k. Hence, the first technique is competitive when D O(n(1/4)) These algorithms match with a result in [2] stating that L(1,1) labelling n-vertex bipartite graphs is hard to approximate within(n1/2-)epsilon, for any epsilon > 0, unless NP=ZPP. We then extend the latter approximation strategy to s-partite graphs, obtaining a (min(h, sk)root n + o(sk root n))-approximation ratio, and to general graphs deriving an (h root n + o(h root n))-approximation algorithm, assuming h >= k. Finally, we prove that the L(h, k)-labelling problem is not easier than coloring the square of a graph
- …
