The three-in-a-tree problem is to determine if a simple undirected graph contains an induced subgraph which is a tree connecting three given vertices. Based on a beautiful characterization that is proved in more than twenty pages, Chudnovsky and Seymour [Combinatorica 2010] gave the previously only known polynomial-time algorithm, running in O(mn 2) time, to solve the three-in-a-tree problem on an n-vertex m-edge graph. Their three-in-a-tree algorithm has become a critical subroutine in several state-of-the-art graph recognition and detection algorithms.

Let $G$ be an $n$-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of $G$ with minimum weight and (2) a cycle of $G$ with minimum weight. The best previously known algorithm for the former problem, running in $O(n\log^3 n)$ time, can be obtained from the algorithm of Ła̧cki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the $O(n\log^3 n)$-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in $O(n\log n\log\log n)$ time via a divide-and-conquer algorithm that finds a shortest nondegenerate cycle. The kernel of our result is an $O(n\log\log n)$-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.

A compression scheme $A$ for a class $\mathbb{G}$ of graphs consists of an encoding algorithm ${\em Encode}_A$ that computes a binary string ${\em Code}_A(G)$ for any given graph $G$ in $\mathbb{G}$ and a decoding algorithm ${\em Decode}_A$ that recovers $G$ from ${\em Code}_A(G)$. A compression scheme $A$ for $\mathbb{G}$ is optimal if both ${\em Encode}_A$ and ${\em Decode}_A$ run in linear time and the number of bits of ${\em Code}_A(G)$ for any $n$-node graph $G$ in $\mathbb{G}$ is information-theoretically optimal to within lower-order terms. Trees and plane triangulations were the only known nontrivial graph classes to admit optimal compression schemes. Based upon Goodrich's separator decomposition for planar graphs and Djidjev and Venkatesan's planarizers for bounded-genus graphs, we give an optimal compression scheme for any hereditary (i.e., closed under taking subgraphs) class $\mathbb{G}$ under the premise that any $n$-node graph of $\mathbb{G}$ to be encoded comes with a genus-$o(\frac{n}{\log^2 n})$ embedding. By Mohar's linear-time algorithm that embeds a bounded-genus graph on a genus-$O(1)$ surface, our result implies that any hereditary class of genus-$O(1)$ graphs admits an optimal compression scheme. For instance, our result yields the first-known optimal compression schemes for planar graphs, plane graphs, graphs embedded on genus-1 surfaces, graphs with genus 2 or less, 3-colorable directed plane graphs, 4-outerplanar graphs, and forests with degree at most 5. For nonhereditary graph classes, we also give a methodology for obtaining optimal compression schemes. From this methodology, we give the first-known optimal compression schemes for triangulations of genus-$O(1)$ surfaces and floorplans.

Matrix $M$ is $k$-concise if the finite entries of each column of $M$ consist of $k$ or fewer intervals of identical numbers. We give an $O(n+m)$-time algorithm to compute the row minima of any $O(1)$-concise $n\times m$ matrix. Our algorithm yields the first $O(n+m)$-time reductions from the replacement-paths problem on an $n$-node $m$-edge undirected graph (respectively, directed acyclic graph) to the single-source shortest-paths problem on an $O(n)$-node $O(m)$-edge undirected graph (respectively, directed acyclic graph). That is, we prove that the replacement-paths problem is no harder than the single-source shortest-paths problem on undirected graphs and directed acyclic graphs. Moreover, our linear-time reductions lead to the first $O(n+m)$-time algorithms for the replacement-paths problem on the following classes of $n$-node $m$-edge graphs: (1) undirected graphs in the word-RAM model of computation, (2) undirected planar graphs, (3) undirected minor-closed graphs, and (4) directed acyclic graphs.

The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an $n$-node unweighted undirected planar graph. The first nontrivial algorithm for the problem, given by Djidjev, runs in $O(n^{5/4}\log n)$ time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to $O(n\log^2 n)$. Weimann and Yuster further reduced the running time to $O(n\log n)$. In this paper, we solve the problem in $O(n)$ time.

We study the problem of determining whether an n-node m-edge graph has an even hole, i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O(n40) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O(n31). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O(n19) time. In this paper, we solve the problem in time O(n11).

We address the problem of designing compact routing tables for an unlabeled connected n-node planar network G. For each node r of G, the designer is given a routing spanning tree $T_r$ of G rooted at r, which specifies the routes for sending packets from r to the rest of G. Each node r of G is equipped with ports $1,2,\ldots,\mathit{deg}_r$, where $\mathit{deg}_r$ is the degree of r in $T_r$. Each port of r is supposed to be assigned to a neighbor of r in $T_r$ in a one-to-one manner. For each node v of G with $v\neq r$, let $\mathit{port}_r(v)$ be the port to which r should forward packets with destination v. Under the assumption that the designer has the freedom to determine the label and the port assignment of each node in G, the routing table design problem is to design a compact routing table $R_r$ for each node r such that $\mathit{port}_r(v)$ can be determined merely from $R_r$ and the label of v. Compact routing tables for various network topologies have been extensively studied in the literature. Planar networks are particularly important for routing with geometric metrics. Based upon four-page decompositions of G, Gavoille and Hanusse gave the best previously known polynomial-time computable result for this problem with linear-space routing tables, where the time complexity is measured under the conventional unit-cost RAM model of computation: Each $\mathit{port}_r(v)$ is computable from $R_r$ and the label of v in $O(\log^{2+\epsilon}n)$ time for any positive constant $\epsilon$. The number of bits required to encode each $R_r$ is at most $8n+o(n)$. The time required to compute each $R_r$ is $O(n)$. Based on orderly spanning trees of G, our design achieves the following improved bounds without increasing the time complexity for computing each $R_r$: Each $\mathit{port}_r(v)$ is computable from $R_r$ and the label of v in $O(\log^{1+\epsilon}n)$ time for any positive constant $\epsilon$. The number of bits required to encode each $R_r$ is at most $7.181n+o(n)$. The overall code length of all n routing tables is at most $7n^2+o(n^2)$ bits.

Energy-efficiency has been an important system issue in hardware and software designs for both real-time embedded systems and server systems. This research explores systems with probabilistic distribution on the execution time of realtime tasks on homogeneous multiprocessor platforms with the capability of dynamic voltage scaling (DVS). The objective is to derive a task partition which minimizes the expected energy consumption for completing all the given tasks in time. We give an efficient 1.13-approximation algorithm and a polynomial-time approximation scheme (PTAS) to provide worst-case guarantees for the strongly NP-hard problem. Experimental results show that the algorithms can effectively minimize the expected energy consumption.

An ordinal tree is an arbitrary rooted tree where the children of each node are ordered. Succinct representations for ordinal trees with efficient query support have been extensively studied. The best previously known result is due to Geary et al. [2004b, pages 1--10]. The number of bits required by their representation for an n -node ordinal tree T is 2 n + o ( n ), whose first-order term is information-theoretically optimal. Their representation supports a large set of O (1)-time queries on T . Based upon a balanced string of 2 n parentheses, we give an improved 2 n + o ( n )-bit representation for T . Our improvement is two-fold: First, the set of O (1)-time queries supported by our representation is a proper superset of that supported by the representation of Geary, Raman, and Raman. Second, it is also much easier for our representation to support new queries by simply adding new auxiliary strings.

Power-aware and energy-efficient designs play important roles for modern hardware and software designs, especially for embedded systems. This paper targets a scheduling problem on a processor with the capability of dynamic voltage scaling (DVS), which could reduce the power consumption by slowing down the processor speed. The objective of the targeting problem is to minimize the average flow time of a set of jobs under a given energy constraint, where the flow time of a job is defined as the interval length between the arrival and the completion of the job. We consider two types of processors, which have a continuous spectrum of the available speeds or have only a finite number of discrete speeds. Two algorithms are given: (1) An algorithm is proposed to derive optimal solutions for processors with a continuous spectrum of the available speeds. (2) A greedy algorithm is designed for the derivation of optimal solutions for processors with a finite number of discrete speeds. The proposed algorithms are extended to cope with jobs with different weights for the minimization of the average weighted flow time. The proposed algorithms are also evaluated with comparisons to schedules which execute jobs at a common effective speed.

Strong connectivity has been an important feature explored in many network applications, such as sensor networks. This research focuses on a dual power assignment problem, where each sensor node has two transmission power levels. The objective is to minimize the number of wireless sensor nodes assigned to transmit messages at the high transmission power level, while the resulting sensor network is strongly connected. We propose an efficient 1.75-approximation algorithm for this challenging problem. We not only show that the approximation ratio of the proposed algorithm is tight but also demonstrate the capability of the proposed algorithm in terms of simulation experiments.

We introduce and study orderly spanning trees of plane graphs. This algorithmic tool generalizes canonical orderings, which exist only for triconnected plane graphs. Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an orderly pair for any connected planar graph G, consisting of an embedded planar graph H isomorphic to G, and an orderly spanning tree of H. We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder's realizer theorem, (2) the first algorithm for computing an area-optimal 2-visibility drawing of a planar graph, and (3) the most compact known encoding of a planar graph with O(1)-time query support. All algorithms in this paper run in linear time.

Variable number of tandem repeats (VNTR) stands for a tandem repeat which has variation in length and the number of repeated segments between individuals. VNTRs are useful as molecule markers in many applications, such as DNA fingerprinting, genetic disease analysis and molecular typing of prokaryotes. It costs a large amount of money and time to identify these special loci by using traditional biological experiments. Here we develop a novel tool, VNTR analyzer, to identify and analyze VNTR in genome sequence by comparing genomic sequences of different strains. In this study, we demonstrate its ability to detect VNTRs by analyzing 3 bacterial species: Staphylococcus aureus, Xylella fastidiosa and Salmonella enterica. The results showed that our program could find VNTRs accurately in a short time. Moreover, the program provides biologists a colorful visualization tool for further analysis.

We propose a new scheme for compressing on image set by building its minimal-cost prediction structure. Existing prediction-based video coding methods can be easily extended and incorporated into this scheme to achieve higher compression efficiency. According to this prediction structure, we also develop a progressive transmission approach for interactive object movie (OM) browsing.

We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers w min and w max and a sequence S of n number pairs (a i ,w i ) with w i > 0. Let segmentS (i,j) of S be the consecutive subsequence of S between indices i and j. The density of S(i,j) is d(i,j) = (a i + a i + 1 + \cdots + a j )/(w i + w i + 1 + \cdots + w j )$. The maximum-density segment problem is to find a maximum-density segment over all segments S(i,j) with w min \leq w i + w i + 1 + \cdots + w j \leq w max . The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu [Proceedings of the Second International Workshop on Algorithms in Bioinformatics, R. Guigó and D. Gusfield, eds., Lecture Notes in Comput. Sci. 2452, Springer-Verlag, New York, 2002, pp. 157--171], runs in O(n log(w max - w min +1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao [J. Comput. System Sci., 65 (2002), pp. 570--586]. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences S representable in O(m) space, we show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(m) time.

Let G be an n-node planar graph. In a visibility representation of G, each node of G is represented by a horizontal line segment such that the line segments representing any two adjacent nodes of G are vertically visible to each other. In the present paper we give the best known compact visibility representation of G. Given a canonical ordering of the triangulated G, our algorithm draws the graph incrementally in a greedy manner. We show that one of three canonical orderings obtained from Schnyder's realizer for the triangulated G yields a visibility representation of G no wider than $\left\lfloor{\frac{22n-40}{15}}\right\rfloor$. Our easy-to-implement O(n)-time algorithm bypasses the complicated subroutines for four-connected components and four-block trees required by the best previously known algorithm of Kant. Our result provides a negative answer to Kant's open question about whether $\left\lfloor{\frac{3n-6}{2}}\right\rfloor$ is a worst-case lower bound on the required width. Also, if G has no degree-three (respectively, degree-five) internal node, then our visibility representation for G is no wider than $\left\lfloor{\frac{4n-9}{3}}\right\rfloor$ (respectively, $\left\lfloor{\frac{4n-7}{3}}\right\rfloor$). Moreover, if G is four-connected, then our visibility representation for G is no wider than n-1, matching the best known result of Kant and He. As a by-product, we give a much simpler proof for a corollary of Wagner's theorem on realizers due to Bonichon, Le Saëc, and Mosbah.

The concept of bus segmentation has been proposed to minimize power consumption by reducing the switched capacitance on each bus [Chen et al. 1999]. This paper details the design theory and implementation issues of segmented bus systems. Based on a graph model and the Gomory-Hu cut-equivalent tree algorithm, a bus can be partitioned into several bus segments separated by pass transistors. Highly communicating devices are placed to adjacent bus segments, so most data communication can be achieved by switching a small portion of the bus segments. Thus, a significant amount of power consumption can be saved. It can be proved that the proposed bus partitioning method achieves an optimal solution. The concept of tree clustering is also proposed to merge bus segments for further power reduction. The design flow, which includes bus tree construction in the register-transfer level and bus segmentation cell placement and routing in the physical level, is discussed for design implementation. The technology has been applied to a μ-controller design, and simulation results by PowerMill show significant improvement in power consumption.

We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property $\pi$ is called a {\em $\pi$-graph}. If $\pi$ satisfies certain properties, then an n-node m-edge $\pi$-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most $\beta(n)+o(\beta(n))$ bits for any continuous superadditive function $\beta(n)$ so that there are at most $2^{\beta(n)+o(\beta(n))}$ distinct n-node $\pi$-graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such $\pi$ include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from $\{1,\ldots, \ell_1\}$ for $\ell_1\leq n$; (5) the edges of G are labeled with labels from $\{1,\ldots, \ell_2\}$ for $\ell_2\leq m$; and (6) each node (respectively, edge) of G has at most $\ell_3=O(1)$ self-loops (respectively, $\ell_4=O(1)$ multiple edges). Moreover, $\ell_3$ and $\ell_4$ are not required to be O(1) for the cases of $\pi$ being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.

Let G be an embedded planar undirected graph that has n vertices, m edges, and f faces but has no self-loop or multiple edge. If G is triangulated, we can encode it using 4/3m-1 bits, improving on the best previous bound of about 1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have been known to suffice. If G is triconnected, we use at most $(2.5+2\log{3})\min\{n,f\}-7$ bits, which is at most 2.835m bits and smaller than the best previous bound of 3m bits. Both of our schemes take O(n) time for encoding and decoding.

This paper proposes a bus-segmentation method that efficiently reduces the switched capacitance on the bus. The power consumed by the bus can, therefore, be substantially reduced. The basic idea of bus segmentation is to partition the bus into several bus segments separated by pass transistors. Highly communicating devices are located to adjacent bus segments, thus, most data communication can be achieved by switching a small portion of the bus segments. As a result, power consumption and critical path delay are both reduced. Experimental results obtained by simulating a delay model and a power model demonstrate that the proposed segmented bus system reduces bus power by about 60%-70% and improves critical bus delay by about 10%-30%.

The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution.Building on this result, Karger, Motwani, and Sudan gave an approximation algorithm for graph coloring that also involves solving a semidefinite program.Solving these semidefinite programs using known methods (ellipsoid, interiorpoint ), though polynomial-time, is quite expensive.We show how they can be approximately solved in ~(nm) time for graphs with n nodes and m edges.