1,720,991 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
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
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
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
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
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
Nuove mappe per territori sempre mutevoli: passeggiate esplorative tra odeporica e informatica
No full textNella letteratura odeporica dato e racconto, narrazione e informazione vivono fortemente
intrecciati. Una delle caratteristiche precipue di questo genere è infatti la continua tensione e interazione tra questi due aspetti, riassumibile nel compito della sensibilità, del punto di vista e delle forme letterarie di veicolare contenuti con forti componenti sia storiche sia geografiche, sia culturali sia scientifiche. A livello strutturale l’odeporica presenta quindi una commistione tra natura documento-centrica e data-centrica, perfettamente declinabile, così come è stata definita nel linguaggio dei new media, nella contrapposizione tra logica del racconto e logica del database. Contrapposizione da cui nascono nuove possibilità espressive, caratterizzanti quello strumento paradossale e figlio del paradosso, in grado al tempo stesso di controllare e creare complessità, che è il medium computazionale
Drawing with colors
No full textIn this paper, we investigate the volume, aspect ratio, angular resolution, edge-separation, and bit-requirement of crossing-free straight-line 3D drawings. We assume the vertex resolution rule, which requires minimum unit distance between any two vertices. Our main result shows that an N-vertex graph colorable with O(1) colors admits a crossing-free straight-line 3D drawing with O(N√N) volume, O(1) aspect ratio,gW(l/N O(1)) angular resolution, Ω (1/N O(1)) edge-separation, and O(log N) bit-requirement, which can be constructed in O(N) time
Influential users in Twitter: detection and evolution analysis
Get PDFIn this paper, we study how to detect the most influential users in the microblogging social network platform Twitter and their evolution over time. To this aim, we consider the Dynamic Retweet Graph (DRG) proposed in Amati et al. (2016) and partially analyzed in Amati et al. (IADIS Int J Comput Sci Inform Syst, 11(2) 2016), Amati et al. (2016). The model of the evolution of the Twitter social network is based here on the retweet relationship. In a DRGs, the last time a tweet has been retweeted we delete all the edges representing this tweet. In this way we model the decay of tweet life in the social platform. To detect the influential users, we consider the central nodes in the network with respect to the following centrality measures: degree, closeness, betweenness and PageRank-centrality. These measures have been widely studied in the static case and we analyze them on the sequence of DRG temporal graphs with special regard to the distribution of the 75% most central nodes. We derive the following results: (a) in all cases, applying the closeness measure results into many nodes with high centrality, so it is useless to detect influential users; (b) for all other measures, almost all nodes have null or very low centrality and (c) the number of vertices with significant centrality are often the same; (d) the above observations hold also for the cumulative retweet graph and, (e) central nodes in the sequence of DRG temporal graphs have high centrality in cumulative graph
- …
