In random-turn games, players toss a coin to decide who moves. This paper studies the complexities of the algorithms for playing random-turn connection games perfectly on regular tessellations. Our study theoretically shows that there are algorithms playing random-turn Hex, Square and Triangle perfectly in${O(n^{9}\cdot 2.618^{n}),\ O(n^{9}\cdot 2.746^{n})}$and${O(n^{9}\cdot 3.645^{n})}$time for each move respectively, where n is the board size. We then implement the perfect-playing algorithm for random-turn Square and measure the actual running time it costs for each move. We then compute and analyze the game lengths on random-turn Square, Hex and Triangle and conjecture that the asymptotic complexity of their game lengths are the same. We finally compare the perfect-playing algorithm with the sampling algorithm by competing against each other, and the numbers of their wins and loses are reported.

Many graphs in real-world applications, such as telecommunications networks, social-interaction graphs and co-authorship graphs, contain temporal information. However, existing graph mining algorithms fail to exploit these temporal information and the resulting subgraph patterns do not contain any temporal attribute. In this paper, we study the problem of mining a set of diversified temporal subgraph patterns from a temporal graph, where each subgraph is associated with the time interval that the pattern spans. This problem motivates important applications such as finding social trends in social networks, or detecting temporal hotspots in telecommunications networks. We propose a divide-and-conquer algorithm along with effective pruning techniques, and our approach runs 2 to 3 orders of magnitude faster than a baseline algorithm and obtains high-quality temporal subgraph patterns in real temporal graphs.

In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1).

A public transportation network can often be modeled as a timetable graph where (i) each node represents a station; and (ii) each directed edge (u,v) is associated with a timetable that records the departure (resp. arrival) time of each vehicle at station u (resp. v). Several techniques have been proposed for various types of route planning on timetable graphs, e.g., retrieving the route from a node to another with the shortest travel time. These techniques, however, either provide insufficient query efficiency or incur significant space overheads.

This paper studies two fundamental problems both of which are defined on a set S of elements drawn from an ordered domain. In the first problem--called approximate K-partitioning--we want to divide S into K disjoint partitions P1, ..., PK such that (i) every element in Pi is smaller than all the elements in Pj for any i, j satisfying 1 ≤ i < j ≤ K, and (ii) the size of each Pi (1 ≤ i ≤ K) falls in a given range [a, b]. In the second problem--called approximate K-splitters---we want to find K - 1 elements s_1, ..., sK-1 from S, such that the size of S ∩ (s_i, s_i-1] falls in a given range [a, b] (define dummy s_0 = - ∞ and s_K = ∞). We present I/O-efficient comparison-based algorithms for solving these problems, and establish their optimality by proving matching lower bounds. Our results reveal that the two problems are separated in terms of I/O complexity when K is small, but have the same hardness when K is large.

With the increase of available protein-protein interaction (PPI) data, more and more efforts have been put to PPI network modeling, and a number of models of PPI networks have been proposed. Roughly speaking, good models of PPI networks should be able to accurately describe PPI mechanisms, and thus reproduce the structures of PPI networks. With such models, theoretical and/or computational biologists can efficiently explore the evolution and dynamics of PPI networks. However, a theoretical and/or computational biologist may feel confused when she/he has to choose a proper PPI model for her/his research work from a dozen of candidate models, while there is no guideline available to help her/him. To tackle this problem, in this article, we carry out a comprehensive performance comparison study on 12 existing models over PPI datasets of four species (yeast, mouse, fruit fly and nematode), by comparing the global and local statistical properties of the original PPI networks and the model-reproduced ones. To draw more convincing conclusions, we use the mean reciprocal rank to combine the ranks of a certain model on all statistical properties. Our experimental results indicate that the PS_Seed model [Solé and Pastor-Satorras (PS) model with seed] the STICKY model and the DD_Seed model (Duplication-Divergence model with seed) fit best with the test PPI datasets. By analyzing the underlying mechanisms of the models with better fitting ability, our analysis shows that the evolutionary mechanism of node duplication and link dynamics and the mechanisms with 'degree-weighted' behaviors seem to be able to describe the PPI networks better.

This paper presents new results in external memory for finding the skyline (a.k.a. maxima) of N points in d-dimensional space. The state of the art uses for fixed d ≥ 3, and O((N/B)logM/B(N/B)) I/Os for d = 2, where M and B are the sizes (in words) of memory and a disk block, respectively. We give algorithms whose running time depends on the number K of points in the skyline. Specifically, we achieve expected cost for fixed d ≥ 3, and O((N/B)logM/B(K/B)) worst-case cost for d = 2. As a side product, we solve two problems both of independent interest. The first one, the M-skyline problem, aims at reporting M arbitrary skyline points, or the entire skyline if its size is at most M. We settle this problem in O(N/B) expected time in any fixed dimensionality d. The second one, the M-pivot problem, is more fundamental: given a set S of N elements drawn from an ordered domain, it outputs M evenly scattered elements (called pivots) from S, namely, S has asymptotically the same number of elements between each pair of consecutive pivots. We give a deterministic algorithm for solving the problem in O(N/B) I/Os.

This paper presents a comprehensive comparison study on the performances of major existing models over two PPI datasets, by comparing the global and local statistical properties of the original PPI networks and the model-reproduced ones. Our experimental results show that the DD model has best fitting ability while iSite model and STICKY model also fit well with the PPI datasets over most statistical properties.