Artículos con la etiqueta ‘Data Structures and Algorithms (cs.DS)’

Arithmetic Algorithms for Hereditarily Binary Natural Numbers

Por • 12 jun, 2013 • Category: Educacion

We study some essential arithmetic properties of a new tree-based number representation, {\em hereditarily binary numbers}, defined by applying recursively run-length encoding of bijective base-2 digits. Our representation expresses giant numbers like the largest known prime number and its related perfect number as well as the largest known Woodall, Cullen, Proth, Sophie Germain and twin primes as trees of small sizes. More importantly, our number representation supports novel algorithms that, in the best case, collapse the complexity of various computations by super-exponential factors and in the worse case are within a constant factor of their traditional counterparts. As a result, it opens the door to a new world, where arithmetic operations are limited by the structural complexity of their operands, rather than their bitsizes.

How hard is it to control an election by breaking ties?

Por • 29 abr, 2013 • Category: sociologia

We study the computational complexity of the problem of controlling the result of an election by breaking ties. When the chair is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections like STV, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Our results contain several surprises. For example, whilst it is NP-hard to compute a manipulating vote for a multi-round rule like Nanson, it is polynomial for the chair to control the result by breaking ties. As a second example, it can be NP-hard to control an election by breaking ties even with a simple two-stage voting rule.

Fast Multi-Scale Detection of Relevant Communities

Por • 15 may, 2012 • Category: sociologia

Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increasing interest as a way to uncover the structure of networks by grouping nodes into communities more densely connected internally than externally. Yet most of the effective methods available do not consider the potential levels of organisation, or scales, a network may encompass and are therefore limited. In this paper we present a method compatible with global and local criteria that enables fast multi-scale community detection. The method is derived in two algorithms, one for each type of criterion, and implemented with 6 known criteria. Uncovering communities at various scales is a computationally expensive task. Therefore this work puts a strong emphasis on the reduction of computational complexity. Some heuristics are introduced for speed-up purposes. Experiments demonstrate the efficiency and accuracy of our method with respect to each algorithm and criterion by testing them against large generated multi-scale networks. This study also offers a comparison between criteria and between the global and local approaches.