Algorithms and Computation

A wireless ad hoc network is a collection of geographically distributed radio nodes which communicate with each other without the support of fixed infrastructure. Wireless ad hoc networks have gained much attention in recent years because their potential wide applications such as environmental monitoring and emergency disaster relief. Some of the key design issues for wireless ad hoc networks include power management, network connectivity and routing. These problems require different formulations and solutions from the classical setting. In this talk, we will look at some sample problems, their mathematical modelling and solutions. It will be seen that graph theory and computational geometry can play a role in the design and analysis of ad hoc networks.

In this talk we will discuss recent work on the modeling and algorithmic analysis of systems involving recursion and probability. There has been intense activity recently in the study of such systems [2,3,10,11,13,14,15,16,17]. The primary motivation comes from the analysis of probabilistic programs with procedures. Probability can arise either due to randomizing steps in the program, or it may reflect statistical assumptions on the behaviour of the program, under which we want to investigate its properties.

Let

S

be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain

S

? Even for a set

S

as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound >1. In this paper we provide the first upper and lower bounds for the embedding problem.

1

Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247.

2

Each embedding of a closed convex curve has dilation ≥ 1.00157.

3

Let

P

be the plane graph that results from intersecting

n

infinite families of equidistant, parallel lines in general position. Then the vertex set of

P

has dilation

$\geq 2/\sqrt{3} \approx 1.1547$

.

Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in

d

-D images (

d

≥ 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several

layered net surface (LNS)

problems captured by an interesting type of geometric graphs called

ordered multi-column graphs

in the

d

-D discrete space (

d

≥ 3). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the

d

-D LNS problem (

d

≥ 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures, and admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related

net surface volume (NSV)

problems of computing well-shaped geometric regions of an optimal total volume in a

d

-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. The practical efficiency and accuracy of the algorithms are showcased by experiments based on real medical data.

We develop exact and approximate algorithms for computing optimal separators and measuring the extent to which two point sets in

d

-dimensional space are separated, with respect to different classes of separators and various extent measures. This class of geometric problems generalizes two widely studied problem families, namely separability and the computation of statistical estimators.

In casting, molten material is poured into the cavity of the cast and allowed to solidify. The cast has two main parts to be removed in opposite parting directions. To manufacture more complicated objects, the cast may also have a side core to be removed in a direction skewed to the parting directions. In this paper, given an object and the parting and side core directions, we give necessary and sufficient conditions to verify whether a cast can be constructed for these directions. In the case of polyhedral objects, we develop a discrete algorithm to perform the test in

O

(

n

3

log

n

) time, where

n

is the object size. If the test result is positive, a cast with complexity

O

(

n

3

) can be constructed within the same time bound. We also present an example to show that a cast may have Θ(

n

3

) complexity in the worst case. Thus, the complexity of our cast is worst-case optimal.

Given a set

S

of

n

points in the plane, and an integer

k

such that 0 ≤

k

<

n

, we show that a geometric graph with vertex set

S

, at most

n

– 1 +

k

edges, and dilation

O

(

n

/ (

k

+ 1)) can be computed in time

O

(

n

log

n

). We also construct

n

–point sets for which any geometric graph with

n

– 1 +

k

edges has dilation Ω(

n

/ (

k

+ 1)); a slightly weaker statement holds if the points of

S

are required to be in convex position.

We introduce a measure for computing the similarity between multiple polylines and a polygon, that can be computed in

O

(

km

2

n

2

) time with a straightforward dynamic programming algorithm. We then present a novel fast algorithm that runs in time

O

(

kmn

log

mn

). Here,

m

denotes the number of vertices in the polygon, and

n

is the total number of vertices in the

k

polylines that are matched against the polygon. The effectiveness of the similarity measure has been demonstrated in a part-based retrieval application with known ground-truth.

Let

V

be a finite set with |

V

|=

n

. A family

$\mathcal{F}\subseteq 2^{V}$

is called

laminar

if for arbitrary two sets

$X, Y \in \mathcal{F}$

,

X

∩

Y

≠ ∅ implies

X

 ⊆ 

Y

or

X

 ⊇ 

Y

. Given a laminar family

$\mathcal{F}$

, a demand function

d

→ℝ

 + 

, and a monotone concave cost function

$F : \mathbb{R}_{+}^{V} \rightarrow \mathbb{R}_{+}$

, we consider the problem of finding a minimum-cost

$x \in \mathbb{R}_{+}^{V}$

such that

x

(

X

)≥

d

(

X

) for all

$X \in \mathcal{F}$

. Here we do not assume that the cost function

F

is differentiable or even continuous. We show that the problem can be solved in O(

n

2

q

) time if

F

can be decomposed into monotone concave functions by the partition of

V

that is induced by the laminar family

$\mathcal{F}$

, where

q

is the time required for the computation of

F

(

x

) for any

$x \in \mathbb{R}_{+}^{V}$

. We also prove that if

F

is given by an oracle, then it takes

${\it \Omega}(n^{2}q)$

time to solve the problem, which implies that our O(

n

2

q

) time algorithm is optimal in this case. Furthermore, we propose an O(

n

log

2

n

) algorithm if

F

is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires

${\it \Omega}(2^{n \over 2}q)$

time when

F

is given implicitly by an oracle, and that it is NP-hard if

F

is given explicitly.

In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than

OPT

+2 and

OPT

+1 respectively, where

OPT

is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.

Given a network modeled as a graph

G

with each link associated with a cost and

k

weights, the Constrained Shortest Path (CSP(

k

)) problem asks for computing a minimum cost path from a source node

s

to a target node

t

satisfying pre-specified bounds on path weights. This problem is NP-hard. In this paper we propose a new approximation algorithm called GEN-LARAC for CSP(

k

) problem based on Lagrangian relaxation method. For

k

= 1, we show that the relaxed problem can be solved by a polynomial time algorithm with time complexity

O

((

m

+

n

log

n

)

2

). Using this algorithm as a building block and combing it with ideas from mathematical programming, we propose an efficient algorithm for arbitrary

k

. We prove the convergence of our algorithm and compare it with previously known algorithms. We point out that our algorithm is also applicable to a more general class of constrained optimization problems.

Given a bipartite graph

$G = (X \dot{\cup} D,E \subseteq X \times D)$

, an

X-perfect matching

is a matching in

G

that covers every node in

X

. In this paper we study the following generalisation of the

X

-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection

$\mathcal{F} \subseteq 2^{X}$

of

k

subsets of

X

, find a subset

M

 ⊆ 

E

of the edges such that for each

$C \in \mathcal{F}$

, the edge set

M

∩ (

C

×

D

) is a

C

-perfect matching in

G

(or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when

k

=

O

(1) and even APX-complete already for

k

=2. On the positive side, we show that a 2/(

k

+1)-approximation can be found in 2

k

poly(

k

,|

X

∪

D

|) time.

Consider a tree

T

of depth 2 whose root has

s

child nodes and the

k

th

child node from left has

n

k

child leaves. Considered as a round-robin tree,

T

represents a schedule in which each page assigned to a leaf under node

k

(1≤

k

≤

s

) appears with period

sn

k

. By varying

s

, we want to maximize the total number

n

=

$\sum_{k=1}^{s}$

n

k

of pages assigned to the leaves with the following constraints: for 1≤

k

≤

s

,

$n_{k} = \lfloor(m + \sum_{j=1}^{ k-1}n_{j} )/s\rfloor$

, where

m

is a given integer parameter. This problem arises in the optimization of a video-on-demand scheme, called

Fixed-Delay Pagoda Broadcasting

.

Due to the floor functions involved, the only known algorithm for finding the optimal

s

is essentially exhaustive, testing

m

/2 different potential optimal values of size

O

(

m

) for

s

. Since computing

n

for a given value of

s

incurs time

O

(

s

), the time complexity of finding the optimal

s

is

O

(

m

2

). This paper analyzes this combinatorial optimization problem in detail and limits the search space for the optimal

s

down to

$\kappa \sqrt{m}$

different values of size

$O \sqrt{m}$

each, where

κ

≈ 0.9, thus improving the time complexity down to

O

(

m

).

Let

G

be a graph with a nonnegative integral function

w

defined on

V

(

G

). A family

$\mathcal{F}$

of subsets of

V

(

G

) (repetition is allowed) is called a

feedback vertex set packing

in

G

if the removal of any member of

$\mathcal{F}$

from

G

leaves a forest, and every vertex

v

∈

V

(

G

) is contained in at most

w

(

v

) members of

$\mathcal{F}$

. The

weight

of a cycle

C

in

G

is the sum of

w

(

v

), over all vertices

v

of

C

. In this paper we characterize all graphs with the property that, for any nonnegative integral function

w

, the maximum cardinality of a feedback vertex set packing is equal to the minimum weight of a cycle.

We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. For trees, Gavoille

et al.

[7] proved that for any such distance labelling scheme, the maximum label length is at least

${1 \over 8} {\rm log}^{2} n - O({\rm log} n)$

bits. They also gave a separator-based labelling scheme that has the optimal label length

${\it \Theta}({\rm log} {n} \cdot {\rm log}(H_{n}(T)))$

, where

H

n

(

T

) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length

${\it \Theta}({\rm log} n \cdot {\rm log} (H_{n}(T)))$

, but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently find the least common ancestor of any two vertices based on their labels only.

In 2000, T. Uno and M. Yagiura published an algorithm that computes all the

K

common intervals of two given permutations of length

n

in

$\mathcal{O}(n+ K)$

time. Our paper first presents a decomposition approach to obtain a compact encoding for common intervals of

d

permutations. Then, we revisit T. Uno and M. Yagiura’s algorithm to yield a linear time algorithm for finding this encoding. Besides, we adapt the algorithm to obtain a linear time modular decomposition of an undirected graph, and thereby propose a formal invariant-based proof for all these algorithms.

Let

G

=(

V

,

E

) be an undirected graph, and let

B

 ⊆ 

V

×

V

be a collection of vertex pairs. We give an incremental polynomial time algorithm to enumerate all minimal edge sets

X

 ⊆ 

E

such that every vertex pair (

s

,

t

) ∈

B

is disconnected in

$(V,E \smallsetminus X)$

, generalizing well-known efficient algorithms for enumerating all minimal

s

-

t

cuts, for a given pair

s

,

t

∈

V

of vertices. We also present an incremental polynomial time algorithm for enumerating all minimal subsets

X

 ⊆ 

E

such that no (

s

,

t

) ∈

B

is a bridge in (

V

,

X

∪

B

). These two enumeration problems are special cases of the more general cut conjunction problem in matroids: given a matroid

M

on ground set

S

=

E

∪

B

, enumerate all minimal subsets

X

 ⊆ 

E

such that no element

b

∈

B

is spanned by

$E \smallsetminus X$

. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (

V

,

E

∪

B

), the enumeration of cut conjunctions for vectorial matroids turns out to be NP-hard.

In an orthogonal drawing of a planar graph

G

, each vertex is drawn as a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments, and any two edges do not cross except at their common end. A bend is a point where an edge changes its direction. A drawing of

G

is called an optimal orthogonal drawing if the number of bends is minimum among all orthogonal drawings of

G

. In this paper we give an algorithm to find an optimal orthogonal drawing of any given series-parallel graph of the maximum degree at most three. Our algorithm takes linear time, while the previously known best algorithm takes cubic time. Furthermore, our algorithm is much simpler than the previous one. We also obtain a best possible upper bound on the number of bends in an optimal drawing.

Let

G

=(

V

,

E

) be an undirected graph with a node set

V

and an arc set

E

.

G

has

k

pairwise disjoint subsets

T

1

,

T

2

,...,

T

k

of nodes, called resource sets, where |

T

i

| is even for each

i

. The partition problem with

k

resource sets asks to find a partition

V

1

and

V

2

of the node set

V

such that the graphs induced by

V

1

and

V

2

are both connected and |

V

1

∩

T

i

|=|

V

2

∩

T

i

|=|

T

i

|/2 holds for each

i

=1,2,...,

k

. The problem of testing whether such a bisection exists is known to be NP-hard even in the case of

k

=1. On the other hand, it is known that that if

G

is (

k

+1)-connected for

k

=1,2, then a bisection exists for any given resource sets, and it has been conjectured that for

k

≥ 3, a (

k

+1)-connected graph admits a bisection. In this paper, we show that for

k

=3, the conjecture does not hold, while if

G

is 4-connected and has

K

4

as its subgraph, then a bisection exists and it can be found in

O

(|

V

|

3

log |

V

|) time. Moreover, we show that for an arc-version of the problem, the (

k

+1)-edge-connectivity suffices for

k

=1,2,3.

Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs, and it is a natural generalization of block graphs (and hence trees). In this paper, a new characterization of ptolemaic graphs is presented. It is a laminar structure of cliques, and leads us to a canonical tree representation, which gives a simple intersection model for ptolemaic graphs. The tree representation is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an

O

(

n

) time algorithm for the Hamiltonian cycle problem.

Let

G

be a fixed undirected graph. The

G

-structure of a graph

F

is the hypergraph

H

with the same set of vertices as

F

and with the property that a set

h

is a hyperedge of

H

if and only if the subgraph of

F

induced on

h

is isomorphic to

G

. For a fixed parameter graph

G

, we consider the complexity of determining whether for a given hypergraph

H

there exists a graph

F

such that

H

is the

G

-structure of

F

. It has been proven that this problem is polynomial if

G

is a path with at most 4 vertices ([9], [10]). We investigate this problem for larger graphs

G

and show that for some

G

the problem is NP-complete – in fact we prove that it is NP-complete for almost all graphs

G

.

This paper addresses the problem of constructing voting protocols that are hard to manipulate. We describe a general technique for obtaining a new protocol by combining two or more base protocols, and study the resulting class of (vote-once) hybrid voting protocols, which also includes most previously known manipulation-resistant protocols. We show that for many choices of underlying base protocols, including some that are easily manipulable, their hybrids are NP-hard to manipulate, and demonstrate that this method can be used to produce manipulation-resistant protocols with unique combinations of useful features.

In this paper, we prove for the first time that the learning complexity of Rocchio’s algorithm is

O

(

d

+

d

2

(log

d

+ log

n

)) over the discretized vector space {0,...,

n

–1}

d

, when the inner product similarity measure is used. The upper bound on the learning complexity for searching for documents represented by a monotone linear classifier (

q

,0) over {0,...,

n

–1}

d

can be improved to

O

(

d

+ 2

k

(

n

–1)(log

d

+ log(

n

–1))), where

k

is the number of nonzero components in

q

. An Ω((

d

2

)log

n

) lower bound on the learning complexity is also obtained for Rocchio’s algorithm over {0,...,

n

–1}

d

. In practice, Rocchio’s algorithm often uses fixed query updating factors. When this is the case, the lower bound is strengthened to 2

$^{{\it \Omega}(d)}$

over the binary vector space {0,1}

d

. In general, if the query updating factors are bounded by

O

(

n

c

) for some constant

c

≥ 0, an

${\it \Omega}(n^{d-1-c}/(n-1))$

lower bound is obtained over {0,...,

n

–1}

d

.

The Correlation Clustering problem has been introduced recently [5] as a model for clustering data when a binary relationship between data points is known. More precisely, for each pair of points we have two scores measuring respectively the similarity and dissimilarity of the two points, and we would like to compute an optimal partition where the value of a partition is obtained by summing up scores of pairs involving points from a same cluster and scores of pairs involving points from different clusters. A closely related problem is Consensus Clustering, where we are given a set of partitions and we would like to obtain a partition that best summarizes the input partitions. The latter problem is a restricted case of Correlation Clustering. In this paper we prove that Min Consensus Clustering is APX-hard even for three input partitions, answering an open question, while Max Consensus Clustering admits a PTAS on instances with a bounded number of input partitions. We exhibit a combinatorial and practical

${4}\over{5}$

-approximation algorithm based on a greedy technique for Max Consensus Clustering on three partitions. Moreover, we prove that a PTAS exists for Max Correlation Clustering when the maximum ratio between two scores is at most a constant.

In this paper we study the problem of scheduling malleable tasks with precedence constraints. We are given

m

identical processors and

n

tasks. For each task the processing time is a function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. The best previous approximation algorithm (that works in two phases) by Lepére et al. [18] has a ratio

$3 + \sqrt{5} \approx 5.236$

. We develop an improved approximation algorithm with a ratio at most

$100/43 + 100(\sqrt{4349} - 7)/2451 \approx 4.730598$

. We also show that our resulting ratio is asymptotically tight.

Given a set of points in the plane, the Minimal Manhattan Network Problem asks for an axis-parallel network that connects every pair of points by a shortest path under

L

1

-norm (Manhattan metric). The goal is to minimize the overall length of the network.

We present an approximation algorithm that provides a solution of length at most 1.5 times the optimum. Previously, the best known algorithm has given only a 2-approximation.

Given a point set

K

of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical, or ± 45° diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture.

As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem.

We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a graph of size

$O({{n^{2}}\over{\varepsilon^{2}}})$

which contains a (1+

ε

)–approximation of a minimum octilinear Steiner tree for every

ε

> 0 and

n

= |

K

|. Hence, we can apply any

α

-approximation algorithm for the Steiner tree problem in graphs (the currently best known bound is

α

≈ 1.55) and achieve an (

α

 + 

ε

)- approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).

We consider the dense subgraph problem that extracts a subgraph with a prescribed number of vertices that has the maximum number of edges (total edge weight in the weighted case) in a given graph. We give approximation algorithms with improved theoretical approximation ratios—assuming that the density of the optimal output subgraph is high, where density is the ratio of number of edges (or sum of edge weights) to the number of edges in the clique on the same number of vertices. Moreover, we investigate the case where the input graph is bipartite, and design a pseudo-polynomial time approximation scheme that can become a PTAS even if the size of the optimal output graph is comparatively small. This is a significant improvement in a theoretical sense, since no constant-ratio approximation algorithm was known previously if the output graph has

o

(

n

) vertices.

Problems of unconditionally secure communication have been studied extensively in network models. Dolev-Dwork-Waarts-Yung considered the Byzantine threats model, in which the adversary can only take over a number of nodes bounded by a threshold. They studied two cases:

1

all communication links (edges in the graph) are two-way communication,

2

all communication links are one-way communication, and there is no feedback.

The node sets that the adversary can take over was generalized by Hirt-Maurer to an adversary structure. At PODC 2002, Kumar-Goundan-Srinathan-Rangan generalized Dolev-Dwork-Waarts-Yung’s first scenario to the case of a general adversary structure. In this paper we generalize Dolev-Dwork-Waarts-Yung’s second scenario to the case of a general adversary structure. As in Dolev-Dwork-Waarts-Yung, our work relies on the use of secret sharing.

Consider an information network with harmful procedures called

attackers

(e.g., viruses); each attacker uses a probability distribution to choose a node of the network to damage. Opponent to the attackers is the

system protector

scanning and cleaning from attackers some part of the network (e.g., an edge or a path), which it chooses independently using another probability distribution. Each attacker wishes to maximize the probability of escaping its cleaning by the system protector; towards a conflicting objective, the system protector aims at maximizing the expected number of cleaned attackers.

We model this network scenario as a non-cooperative strategic game on graphs. We focus on the special case where the protector chooses a single edge. We are interested in the associated

Nash equilibria,

where no network entity can unilaterally improve its local objective. We obtain the following results:

– No instance of the game possesses a pure Nash equilibrium.

–Every mixed Nash equilibrium enjoys a graph-theoretic structure, which enables a (typically exponential) algorithm to compute it.

– We coin a natural subclass of mixed Nash equilibria, which we call

matching Nash equilibria,

for this game on graphs. Matching Nash equilibria are defined using structural parameters of graphs, such as independent sets and matchings.

–We derive a characterization of graphs possessing matching Nash equilibria. The characterization enables a linear time algorithm to compute a matching Nash equilibrium on any such graph with a given independent set and vertex cover.

– Bipartite graphs are shown to satisfy the characterization. So, using a polynomial-time algorithm to compute a perfect matching in a bipartite graph, we obtain, as our main result, an efficient graph-theoretic algorithm to compute a matching Nash equilibrium on any instance of the game with a bipartite graph.

This paper presents the SkipTree, a new balanced, distributed data structure for storing data with multidimensional keys in a peer-to-peer network. The SkipTree supports range queries as well as single point queries which are routed in

O

(log

n

) hops. SkipTree is fully decentralized with each node being connected to

O

(log

n

) other nodes. The memory usage for maintaining the links at each node is

O

(log

n

log log

n

) on average and

O

(log

2

n

) in the worst case. Load balance is also guaranteed to be within a constant factor.

Reducing the error of quantum algorithms is often achieved by applying a primitive called amplitude amplification. Its use leads in many instances to quantum algorithms that are quadratically faster than any classical algorithm. Amplitude amplification is controlled by choosing two complex numbers

φ

s

and

φ

t

of unit norm, called phase factors. If the phases are well-chosen, amplitude amplification reduces the error of quantum algorithms, if not, it may increase the error. We give an analysis of amplitude amplification with a emphasis on the influence of the phase factors on the error of quantum algorithms. We introduce a so-called phase matrix and use it to give a straightforward and novel analysis of amplitude amplification processes. We show that we may always pick identical phase factors

φ

s

=

φ

t

with argument in the range

${{\pi}\over{3}}{\leq} {\rm arg}(\phi_{s}){\leq} {\pi}$

. We also show that identical phase factors

φ

s

=

φ

t

with

$-{{\pi}\over{2}}< {\rm arg}(\phi_{s})< {{\pi}\over{2}}$

never leads to an increase in the error, generalizing a recent result of Lov Grover who shows that amplitude amplification becomes a quantum analogue of classical repetition if we pick phase factors

φ

s

=

φ

t

with

${\rm arg}(\phi_{s}) = {{\pi}\over{3}}$

.

We present the interpolation search tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in

O

(1) worst-case (w.c.) block transfers and search operations in

O

(log

B

log

n

) expected block transfers, where

B

represents the disk block size and

n

denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The w.c. search bound of our indexing scheme is

O

(log

B

n

) block transfers. Our update and expected search bounds constitute a considerable improvement over the

O

(log

B

n

) w.c. block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also suggested by a set of preliminary experiments we have carried out. Our indexing scheme is based on an externalization of a main memory data structure based on interpolation search.

In this paper we present space-query trade-offs for external memory data structures that answer shortest path queries on planar directed graphs. For any

$S = {\it \Omega}(N^{1 + \epsilon}$

) and

S

 = 

O

(

N

2

/

B

), our main result is a family of structures that use

S

space and answer queries in

$O({{N^{2}}\over{SB}})$

I/Os, thus obtaining optimal space-query product

O

(

N

2

/

B

). An

S

space structure can be constructed in

$O(\sqrt{S}\cdot {\rm sort}(N))$

I/Os, where sort(

N

) is the number of I/Os needed to sort

N

elements,

B

is the disk block size, and

N

is the size of the graph.

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text

T

of length

n

over a fixed alphabet

A

, we can preprocess

T

and give an

$O(n\sqrt{{\rm log} n})$

-bit space data structure so that, for any query pattern

P

of length

m

, we can find all 1-mismatch (or 1-difference) occurrences of

P

in

O

(

m

log log

n

+

occ

) time, where

occ

is the number of occurrences. This is the fastest known query time given that the space of the data structure is

o

(

n

log

2

n

) bits.

The space of our data structure can be further reduced to

O

(

n

) if we can afford a slow down factor of log

ε

n

, for 0 <

ε

≤ 1. Furthermore, our solution can be generalized to solve the

k

-mismatch (and the

k

-difference) problem in

O

(|

A

|

k

m

k

(

k

+log log

n

) +

occ

) and

O

(log

ε

n

(|

A

|

k

m

k

(

k

+log log

n

) +

occ

)) query time using an

$O(n\sqrt{{\rm log} n})$

-bit and an

O

(

n

)-bit indexing data structures, respectively.

A

continuous query

is a standing query over a dynamic data set whose query result needs to be constantly updated as new data arrive. We consider the problem of constructing a data structure on a set of continuous

band-join

queries over two data sets

R

and

S

, where each band-join query asks for reporting the set { (

r

,

s

)∈

R

×

S

|

a

≤

r

–

s

≤

b

} for some parameters

a

and

b

, so that given a data update in

R

or

S

, one can quickly identify the subset of continuous queries whose results are affected by the update, and compute changes to these results.

We present the first nontrivial data structure for this problem that simultaneously achieves subquadratic space and sublinear query time. This is achieved by first decomposing the original problem into two independent subproblems, and then carefully designing data structures suitable for each case, by exploiting the particular structure in each subproblem.

A key step in the above construction is a data structure whose performance increases with the degree of

clusteredness

of the band-joins being indexed. We believe that this structure is of independent interest and should have broad impact in practice. We present the details in [1].

In this paper, we formulate a class of colored range query problems to model the multi-dimensional range queries in the presence of categorical information. By applying appropriate sketching techniques on our framework, we obtained efficient data structures that provide approximate solutions to these problems. In addition, the framework can be employed to attack other related problems by finding the appropriate summary structures.

We study the complexity and approximation of the problem of reconstructing haplotypes from genotypes on pedigrees under the Mendelian Law of Inheritance and the minimum recombinant principle (MRHC). First, we show that MRHC for simple pedigrees where each member has at most one mate and at most one child (

i.e.

binary-tree pedigrees) is NP-hard. Second, we present some approximation results for the MRHC problem, which are the first approximation results in the literature to the best of our knowledge. We prove that MRHC on two-locus pedigrees or binary-tree pedigrees with missing data cannot be approximated (the formal definition is given in section 1.2) unless P=NP. Next we show that MRHC on two-locus pedigrees without missing data cannot be approximated within any constant ratio under the Unique Games Conjecture and can be approximated within ratio O

$(\sqrt{{\rm log}(n)})$

. Our L-reduction for the approximation hardness gives a simple alternative proof that MRHC on two-locus pedigrees is NP-hard, which is much easier to understand than the original proof. We also show that MRHC for tree pedigrees without missing data cannot be approximated within any constant ratio under the Unique Games Conjecture, too. Finally, we explore the hardness and approximation of MRHC on pedigrees where each member has a bounded number of children and mates mirroring real pedigrees.

In this paper we present techniques to significantly improve the space complexity of several ordered tree comparison algorithms without sacrificing the corresponding time complexity. We present new algorithms for computing the constrained ordered tree edit distance and the alignment of (ordered) trees. The techniques can also be applied to other related problems.

The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a 1.75-approxi- mation algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [1].

Consider two phylogenetic networks

N

and

N

′ of size

n

. The tripartition-based distance finds the proportion of tripartitions which are not shared by

N

and

N

′. This distance is proposed by Moret et al (2004) and is a generalization of Robinson-Foulds distance, which is orginally used to compare two phylogenetic trees. This paper gives an

O

(min{

kn

log

n

,

n

log

n

 + 

hn

})-time algorithm to compute this distance, where

h

is the number of hybrid nodes in

N

and

N

′ while

k

is the maximum number of hybrid nodes among all biconnected components in

N

and

N

′. Note that

k

<<

h

<<

n

in a phylogenetic network. In addition, we propose algorithms for comparing galled-trees, which are an important, biological meaningful special case of phylogenetic network. We give an

O

(

n

)-time algorithm for comparing two galled-trees. We also give an

O

(

n

+

kh

)-time algorithm for comparing a galled-tree with another general network, where

h

and

k

are the number of hybrid nodes in the latter network and its biggest biconnected component respectively.

The 2-

Interval Pattern problem

is to find the largest constrained pattern in a set of 2-intervals. The constrained pattern is a subset of the given 2-intervals such that any pair of them are

R

-comparable, where model

$R \subseteq \{<, \sqsubset, \between \}$

. The problem stems from the study of general representation of RNA secondary structures. In this paper, we give three improved algorithms for different models. Firstly, an

$O(n {\rm log} n+\mathcal{L})$

algorithm is proposed for the case

$R = \{\between\}$

, where

$\mathcal{L}$

=

O

(

dn

)=

O

(

n

2

) is the total length of all 2-intervals (density

d

is the maximum number of 2-intervals over any point). This improves previous

O

(

n

2

log

n

) algorithm. Secondly, we use dynamic programming techniques to obtain an

O

(

n

log

n

+

dn

) algorithm for the case

$R = \{ <, \sqsubset\}$

, which improves previous

O

(

n

2

) result. Finally, we present another

$O(n {\rm log} n + \mathcal{L})$

algorithm for the case

$R = \{\sqsubset, \between\}$

with disjoint support(interval ground set), which improves previous

$O(n^{2}\sqrt{n})$

upper bound.

In semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. This may not be true in some application. This paper considers semi-online problems on identical machines with inexact partial information. Three problems are considered, where we know in advance that the optimal value, or the largest job size are in given intervals, respectively, while their exact values are unknown. We give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter

r

 ∈ [1, ∞ ). We establish that for which

r

the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. Optimal preemptive semi-online algorithms are then obtained.

In this paper, we study the on-line version of maximum-weighted hereditary subgraph problems. In our on-line model, the final instance-graph (which has

n

vertices) is revealed in

t

clusters, 2 ≤

t

≤

n

. We first focus on the on-line version of the following problem: finding a maximum-weighted subgraph satisfying some hereditary property. Then, we deal with the particular case of the independent set. For all these problems, we are interested in two types of results: the competitivity ratio guaranteed by the on-line algorithm and hardness results that account for the difficulty of the problems and for the quality of algorithms developed to solve them.

In this study, a novel adaptive learning algorithm for feed-forward network based on optimized instantaneous learning rates is proposed to predict stock market movements. In this new algorithm, the optimized adaptive learning rates are used to adjust the weight changes dynamically. For illustration and testing purposes the proposed algorithm is applied to two main stock price indices: S&P 500 and Nikkei 225. The experimental results reveal that the proposed algorithm provides a promising alternative to stock market prediction.

Some kind of discrete data sets can be practically transformed into uniform by the related distribution function. By addressing the sparsity of data which measures the discreteness, this paper demonstrates that the sparsity decides the uniformity of the transformed data, and that could be a good reason to explain both the success of the bucket sort in PennySort 2003 and the failure for the same algorithm with the data modified. So the sparsity provides a good criterion to predict whether the algorithm works or not.

We develop an algorithm for computing the equilibrium price in the Fisher’s exchange market model with logarithmic utility functions. The algorithm is proved to converge to the equilibrium price in finite time and performs better than existing polynomial-time algorithms in experimental tests.

A partition of a set of

n

items is a grouping of the items into

k

disjoint classes of equal size. Any partition can be modeled as a graph: the items become the vertices of the graph and two vertices are connected by an edge if and only if the associated items belong to the same class. In a planted partition model a graph that models the planted partition is obscured by random noise, i.e., edges within a class can get removed and edges between classes can get inserted at random. We study the task to reconstruct the planted partition from this graph whose complexity can be controlled by the number

k

of classes if the noise level is fixed. The best bounds on

k

where the classes can be reconstructed correctly almost surely are achieved by spectral algorithms. We show that a combination of random sampling and iterating the spectral approach can boost its performance in the sense that the number of classes that can be reconstructed correctly asymptotically almost surely can be as large as

$k = c\sqrt{n}/{\rm loglog}n$

for some constant

c

. This extends the range of

k

for which such guarantees can be given for any efficient algorithm.

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity.

We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions.

On the one hand, we prove tight lower and upper bounds of roughly

${\it \Theta}(\sqrt{n})$

for the expected height of binary search trees under partial permutations and partial alterations. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.

In this work we consider the problem of finding Hamilton Cycles in graphs derived from the uniform random intersection graphs model

G

n

,

m

,

p

. In particular, (a) for the case

m

 = 

n

α

,

α

> 1 we give a result that allows us to apply (with the same probability of success) any algorithm that finds a Hamilton cycle with high probability in a

G

n

,

k

graph (i.e. a graph chosen equiprobably form the space of all graphs with

k

edges), (b) we give an

expected polynomial time

algorithm for the case

p

= constant and

$m \leq \alpha {\sqrt{{n}\over {{\rm log}n}}}$

for some constant

α

, and (c) we show that the greedy approach still works well even in the case

$m = o({{n}\over{{\rm log}n}})$

and

p

just above the connectivity threshold of

G

n

,

m

,

p

(found in [21]) by giving a greedy algorithm that finds a Hamilton cycle in those ranges of

m

,

p

with high probability.

We present two novel algorithms for tracking the number of distinct items over high speed data streams consisting of insertion and deletion operations that improves on the space and time complexity of existing algorithms.

Given a sequence of

n

real numbers

A

=

a

1

,

a

2

,...,

a

n

and a positive integer

k

, the

Sum Selection Problem

is to find the segment

A

(

i

,

j

) = 

a

i

,

a

i

 + 1

,...,

a

j

such that the rank of the sum

$s(i, j) = \sum_{t = i}^{j}{a_{t}}$

is

k

over all

${n(n-1)} \over {2}$

segments. We will give a randomized algorithm for this problem that runs in expected

O

(

n

log

n

) time. Applying this algorithm we can obtain an algorithm for the

k

Maximum Sums Problem

, i.e., the problem of enumerating the

k

largest sum segments, that runs in expected

O

(

n

log

n

+

k

) time. The previously best known algorithm for the

k

Maximum Sums Problem

runs in

O

(

n

log

2

n

+

k

) time in the worst case.

Motivated by the peer-to-peer content sharing systems in large-scale networks, we will study interval routing schemes in Erdös-Rényi random graphs. C. Gavoille and D. Peleg [13] posed an open question of whether almost all networks support a shortest-path interval routing scheme with 1 interval. In this paper, we answer this question partially by proving that in almost all networks, there is an interval routing scheme with 1 interval up to additive stretch 2. Our proof is based on the properties of dominating cliques in random graphs.

In this paper we address the problem of estimating the number of stations in a wireless network. Under the assumption that each station can detect collisions, we show that it is possible to estimate the number stations in the network within a factor 2 from the correct value in time

O

(log

n

log log

n

). We further show that if no station can detect collisions, the same task can be accomplished within a factor of 3 in time

O

(log

2

n

) and maximum energy

O

(log

n

) per node, with high probability. Finally, we present an algorithm that computes the minimum value held by the stations in the wireless network in time

O

(log

2

n

).

The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model due to the fundamental nature of the problem. Several randomized algorithms are known for sorting. Most of the prior algorithms suffer from undue complications in memory layouts, implementation, or lack of tight analysis. In this paper we present a simple randomized algorithm that sorts in optimal time

with high probablity

and has all the desirable features for practical implementation.

In this paper, we propose two efficient parallel algorithms for constructing a

k

-tree center and a

k

-tree core of a tree network, respectively. Both algorithms take

O

(log

n

) time using

O

(

n

) work on the EREW PRAM. Our algorithms improve the algorithms previously proposed by Wang (IEEE Trans. Par. Dist. Sys. 1998) and Peng et al. (J. Algorithms 1993).

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of host computers, and assume that a user host can receive the service if at least one adjacent host computer (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees with

n

hosts, ⌈(

n

+1)/2⌉ mobile servers are necessary and sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with

n

hosts, ⌈(

n

+1)/3⌉ mobile servers are necessary and sufficient.

We show that the number of minimal dominating sets in a graph on

n

vertices is at most 1.7697

n

, thus improving on the trivial

$\mathcal{O}(2^{n}/\sqrt{n})$

bound. Our result makes use of the measure and conquer technique from exact algorithms, and can be easily turned into an

$\mathcal{O}(1.7697^{n})$

listing algorithm.

Based on this result, we derive an

$\mathcal{O}(2.8805^{n})$

algorithm for the domatic number problem, and an

$\mathcal{O}(1.5780^{n})$

algorithm for the minimum-weight dominating set problem. Both algorithms improve over the previous algorithms.

In this paper we study collective additive tree spanners for special families of graphs including planar graphs, graphs with bounded genus, graphs with bounded tree-width, graphs with bounded clique-width, and graphs with bounded chordality. We say that a graph

G

=(

V

,

E

)

admits a system of μ

collective additive tree r

-spanners

if there is a system

$\mathcal{T}(G)$

of at most

μ

spanning trees of

G

such that for any two vertices

x

,

y

of

G

a spanning tree

$T \in \mathcal{T}(G)$

exists such that

d

T

(

x

,

y

)≤

d

G

(

x

,

y

)+

r

. We describe a general method for constructing a ”small” system of collective additive tree

r

-spanners with small values of

r

for ”well” decomposable graphs, and as a byproduct show (among other results) that any weighted planar graph admits a system of

$O(\sqrt{n})$

collective additive tree 0–spanners, any weighted graph with tree-width at most

k

–1 admits a system of

k

log

2

n

collective additive tree 0–spanners, any weighted graph with clique-width at most

k

admits a system of

k

log

3/2

n

collective additive tree (2

w

)–spanners, and any weighted graph with size of largest induced cycle at most

c

admits a system of log

2

n

collective additive tree

$(2\lfloor{c/2}\rfloor{\sf w})$

–spanners and a system of 4log

2

n

collective additive tree

$(2(\lfloor{c/3}\rfloor{+1}){\sf w})$

–spanners (here,

w

is the maximum edge weight in

G

). The latter result is refined for weighted weakly chordal graphs: any such graph admits a system of 4 log

2

n

collective additive tree (2

w

)-spanners. Furthermore, based on this collection of trees, we derive a compact and efficient routing scheme for those families of graphs.

We present an expected polynomial time algorithm to generate a 2-connected

unlabeled

planar graph uniformly at random. To do this we first derive recurrence formulas to count the exact number of

rooted

2-connected planar graphs, based on a decomposition along the connectivity structure. For 3-connected planar graphs we use the fact that they have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a

sense-reversing

or a

pole-exchanging

automorphism. We prove a bijection between such symmetric objects and certain

colored networks

. These colored networks can again be decomposed along their connectivity structure. All the numbers can be evaluated in polynomial time by dynamic programming. To generate 2-connected unlabeled planar graphs

without a root

uniformly at random we apply

rejection sampling

and obtain an expected polynomial time algorithm.

In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph

G

such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees,

s

–

t

paths, cycles, matchings, and

κ

-factors for

κ

∈ {1,2}. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of

k

1 − 

ε

for any

ε

> 0, where

k

is the number of crossings in

G

. We then show that the problems are fixed-parameter tractable if we use the number of crossings in the given graph as the parameter. Finally we present a simple but effective heuristic for spanning trees.

The paper deals with the problem of modeling a

k

-regular topology over an existing network architecture by establishing virtual point-to-point communication paths, referred to as

k-routing.

We consider the question of the existence and minimisation of edge spread of

k

-routings with bounded edge load in undirected networks. Efficient algorithms are presented for determining minimal

k

-routings with edge load 1 and for certain cases with edge load 2. On the negative side, the problems of finding a 6-routing with load 2 and of minimising a 2-routing with load 2 are proven to be

NP

-hard (though the latter is approximable within 7/6). The results imply the

NP

-hardness of the well known all-to-all routing problem for bounded edge load.

We study the computational complexity of decision and optimization problems that may be expressed as boolean contraint satisfaction problem with the global cardinality constraints. In this paper we establish a characterization theorem for the decision problems and derive some new approximation hardness results for the corresponding global optimization problems.

We study the computational complexity of deciding the existence of a Pure Nash Equilibrium or a subgame perfect Nash equilibrium with a given payoff and other related problems in finite multi-player extensive games with perfect information. We propose three ways of representing a game with different degrees of succinctness for the components of the game. We show that when the number of moves of each player is large and the player function and the utilities are represented succinctly the considered problems are

PSPACE

-complete. In contraposition, when the game is described extensively by means of its associated tree all the problems are decidable in polynomial time.

We improve an upper bound by Hirsch on a deterministic algorithm for solving general CNF satisfiability problem. With more detail analysis of Hirsch’s algorithm, we give some improvements, by which we can prove an upper bound

$\tilde{\mathcal{O}}(1.234^{m})$

w.r.t. the number

m

of input clauses, which improves Hirsch’s bound

$\tilde{\mathcal{O}}(1.239^{m})$

.

We show that the NP-hard optimization problem minimum weight exact satisfiability for a CNF formula over

n

propositional variables equipped with arbitrary real-valued weights can be solved in time

O

(2

0.2441

n

). To the best of our knowledge, the algorithm presented here is the first handling the weighted XSAT optimization version in non-trivial worst case time.

We study the problem of finding a longest common increasing subsequence (LCIS) of multiple sequences of numbers. The LCIS problem is a fundamental issue in various application areas, including the whole genome alignment and pattern recognition. In this paper we give an efficient algorithm to find the LCIS of two sequences in

O

(min(

r

logℓ,

n

ℓ + 

r

)loglog

n

 + 

n

log

n

) time where

n

is the length of each sequence and

r

is the total number of ordered pairs of positions at which the two sequences match and ℓ is the length of the LCIS. For

m

sequences where

m

≥ 3, we find the LCIS in

O

(min(

mr

2

,

mr

log ℓlog

m

r

) + 

mn

log

n

) time where

r

is the total number of

m

-tuples of positions at which the

m

sequences match. The previous results find the LCIS of two sequences in

O

(

n

2

) and

O

(

n

ℓ log

n

) time. Our algorithm is faster when

r

is relatively small, e.g., for

r

 < min(

n

2

/loglog

n

,

n

ℓ).

We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the

Pareto curve

and (ii) the so-called

decision maker’s approach

in which both criteria are combined into a single (usually non-linear) objective function. Previous work by Papadimitriou and Yannakakis showed how to efficiently approximate the Pareto curve for problems like

Shortest Path

,

Spanning Tree

, and

Perfect Matching

. We wish to determine for which classes of combined objective functions the approximate Pareto curve also yields an approximate solution to the decision maker’s problem. We show that an

FPTAS

for the Pareto curve also gives an

FPTAS

for the decision maker’s problem if the combined objective function is growth bounded like a quasi-polynomial function. If these functions, however, show exponential growth then the decision maker’s problem is NP-hard to approximate within any factor. In order to bypass these limitations of approximate decision making, we turn our attention to Pareto curves in the probabilistic framework of smoothed analysis. We show that in a smoothed model, we can efficiently generate the (complete and exact) Pareto curve with a small failure probability if there exists an algorithm for generating the Pareto curve whose worst case running time is pseudopolynomial. This way, we can solve the decision maker’s problem w.r.t. any non-decreasing objective function for randomly perturbed instances of, e.g.,

Shortest Path

,

Spanning Tree

, and

Perfect Matching

.

We consider

min set covering

when the subsets are constrained to have maximum cardinality three. We propose an exact algorithm whose worst case complexity is bounded above by

O

*

(1.4492

n

).

In this paper, we provide efficient algorithms for solving the weighted center problems in a cactus graph. In particular, an

O

(

n

log

n

) time algorithm is proposed that finds the weighted 1-center in a cactus graph, where

n

is the number of vertices in the graph. For the weighted 2-center problem, an

O

(

n

log

3

n

) time algorithm is devised for its continuous version and showed that its discrete version is solvable in

O

(

n

log

2

n

) time. No such algorithm was previously known. The obnoxious center problem in a cactus graph can now be solved in

O

(

n

log

3

n

). This improves the previous result of

O

(

cn

) where

c

is the number of distinct vertex weights used in the graph [8]. In the worst case

c

is

O

(

n

).

An

ordered labeled tree

is a rooted tree, where the left-to-right order among

siblings

is significant and each node associates a label. A

forest

is a sequence of ordered labeled trees. Suppose

F

is a forest. A

substructure

is a connected subgraph of

F

. Define a

subforest

as a sequence of substructures of

F

such that their roots are siblings. The

local forest similarity

problem for forests

F

and

G

is to find two most similar subforests of

F

and

G

. We answer an open problem in Paper [3], and provide efficient algorithms on it. Comparing with previous results, our algorithms achieve better performance.

We derive fast algorithms for the problem of finding, on the real line, a prescribed number of intervals of maximum total length that contain at most some prescribed number of points from a given point set. Basically this is a typical dynamic programming problem, however, for input sizes much bigger than the two parameters we can improve the obvious time bound by selecting a restricted set of candidate intervals that are sufficient to build some optimal solution. As a byproduct, the same idea improves an algorithm for a similar subsequence problem recently brought up by Chen, Lu and Tang at IWBRA 2005. The problems are motivated by the search for significant patterns in certain biological data. While the algorithmic idea for the asymptotic worst-case bound is rather evident, we also consider further heuristics to save even more time in typical instances. One of them, described in this paper, leads to an apparently open problem of computational geometry flavour (where we are seeking a subquadratic algorithm) which might be interesting in itself.

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM’01), (Pisanti et al.,MFCS’03) and (Pelfrene et al., CPM’03), its output-polynomial time computability is still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length

n

with

O

(

n

3

) time per motif with

O

(

n

2

) space and

O

(

n

3

) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach.

Reconstruction of an evolutionary history for a set of organisms is an important research subject in computational biology. One approach motivated by graph theory constructs a relationship graph based on pairwise evolutionary closeness. The approach builds a tree representation equivalent to this graph such that leaves, corresponding to the organisms, are within a specified distance of

k

in the tree if connected in the relationship graph. This problem, the

k

-th phylogenetic root construction, has known linear time algorithms for

k

≤ 4. However, the computational complexity is unknown when

k

≥ 5. We present a polynomial time algorithm for strictly chordal relationship graphs when

k

= 5.

We characterize the gap between time and space complexity of functions by operators and completeness. First, we introduce a new notion of operators for function complexity classes based on recursive function theory and construct an operator which generates

FPSPACE

from

FP

. Then, we introduce new function classes composed of functions whose output lengths are bounded by the input length plus some constant. We characterize

FP

and

FPSPACE

by using these classes and operators. Finally, we define a new notion of completeness for

FPSPACE

and show a

FPSPACE

-complete function.

Given a graph

G

=(

V

,

E

) with |

V

|=

n

, we consider the following problem. Place

n

points on the vertices of

G

independently and uniformly at random. Once the points are placed, relocate them using a bijection from the points to the vertices that minimizes the maximum distance between the random place of the points and their target vertices.

We look for an upper bound on this maximum relocation distance that holds with high probability (over the initial placements of the points).

For general graphs, we prove the #

P

-hardness of the problem and that the maximum relocation distance is

$O(\sqrt{n})$

with high probability. We also present a Fully Polynomial Randomized Approximation Scheme when the input graph admits a polynomial-size family of witness cuts while for trees we provide a 2-approximation algorithm.

In a breakthrough result, Reingold [17] showed that the Undirected

st

-Connectivity problem can be solved in

O

(log

n

) space. The next major challenge in this direction is whether one can extend it to directed graphs, and thereby lowering the deterministic space complexity of

$\mathcal{RL}$

or

$\mathcal{NL}$

. In this paper, we show that Reingold’s algorithm, the

O

(log

4/3

n

)-space algorithm by Armoni et al.[3] and the

O

(log

3/2

n

)-space algorithm by Nisan et al.[14] can all be carried out on the RAM-NNJAG model [15](a uniform version of the NNJAG model [16]). As there is a tight Ω(log

2

n

) space lower bound for the Directed

st

-Connectivity problem on the RAM-NNJAG model implied by [8], our result gives an obstruction to generalizing Reingold’s algorithm to the directed case.

We present upper bounds on the computational power of an optical model of computation called the

$\mathcal{C}_{2}$

-CSM. We show that

$\mathcal{C}_{2}$

-CSM time is no more powerful than sequential space, thus giving one of the two inclusions that are necessary to show that the model verifies the parallel computation thesis. Furthermore we show that

$\mathcal{C}_{2}$

-CSMs that simultaneously use polynomial space and polylogarithmic time decide no more than the class

NC

.

This paper investigates the complexity of the min-max and min-max regret versions of the

s

–

t

min cut and min cut problems. Even if the underlying problems are closely related and both polynomial, we show that the complexity of their min-max and min-max regret versions, for a constant number of scenarios, are quite contrasted since they are respectively strongly

NP

-hard and polynomial. Thus, we exhibit the first polynomial problem,

s

–

t

min cut, whose min-max (regret) versions are strongly

NP

-hard. Also, min cut is one of the few polynomial problems whose min-max (regret) versions remain polynomial. However, these versions become strongly

NP

-hard for a non constant number of scenarios. In the interval data case, min-max versions are trivially polynomial. Moreover, for min-max regret versions, we obtain the same contrasted result as for a constant number of scenarios: min-max regret

s

–

t

cut is strongly

NP

-hard whereas min-max regret cut is polynomial.

Given a sequence of

n

real numbers and an integer

k

,

$1 \leq k \leq {1 \over 2}n(n - 1)$

, the

k

maximum-sum segments problem is to locate the

k

segments whose sums are the

k

largest among all possible segment sums. Recently, Bengtsson and Chen gave an

$O({\rm min}\{k+n{\rm log}^{2}n,n\sqrt{k}\})$

-time algorithm for this problem. In this paper, we propose an

O

(

n

 + 

k

log(min{

n

,

k

}))-time algorithm for the same problem which is superior to Bengtsson and Chen’s when

k

is

o

(

n

log

n

). We also give the first optimal algorithm for delivering the

k

maximum-sum segments in non-decreasing order if

k

≤

n

. Then we develop an

O

(

n

2

d

 − 1

 + 

k

logmin{

n

,

k

})–time algorithm for the

d

-dimensional version of the problem, where

d

>1 and each dimension, without loss of generality, is of the same size

n

. This improves the best previously known

O

(

n

2

d

 − 1

C

)-time algorithm, also by Bengtsson and Chen, where

$C = {\rm min}\{k + n {\rm log}^{2} n, n{\sqrt{k}}\}$

. It should be pointed out that, given a two-dimensional array of size

m

×

n

, our algorithm for finding the

k

maximum-sum subarrays is the first one achieving cubic time provided that

k

is

$O({{m^{2}n} \over {{\rm log} n }})$

.

We study

network load games

, a class of routing games in networks which generalize selfish routing games on networks consisting of parallel links. In these games, each user aims to route some traffic from a source to a destination so that the maximum load she experiences in the links of the network she occupies is minimum given the routing decisions of other users. We present results related to the existence, complexity, and price of anarchy of Pure Nash Equilibria for several network load games. As corollaries, we present interesting new statements related to the complexity of computing equilibria for selfish routing games in networks of restricted parallel links.

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that it is NP-hard to find a coloring whose entropy is within

$({1 \over 7} - \epsilon){\rm log} n$

of the chromatic entropy for any

ε

> 0, where

n

is the number of vertices of the graph. A simple polynomial case is also identified. It is known that the traditional graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem.

We here study

max hamming xsat

, i.e., the problem of finding two

xsat

models at maximum Hamming distance. By using a recent

xsat

solver as an auxiliary function, an

O

(2

n

) time algorithm can be constructed, where

n

is the number of variables. This upper time bound can be further improved to

O

(1.8348

n

) by introducing a new kind of branching, more directly suited for finding models at maximum Hamming distance. The techniques presented here are likely to be of practical use as well as of theoretical value, proving that there are non-trivial algorithms for maximum Hamming distance problems.

In this paper we study the notion of the Evolutionary Stable Strategies (ESS) in evolutionary games and we demonstrate their qualitative difference from the Nash Equilibria, by showing that a random evolutionary game has on average

exponentially less

number of ESS than the number of Nash Equilibria in the underlying symmetric 2-person game with random payoffs.

Let

G

be a graph embedded in Euclidean space. For any two vertices of

G

their

dilation

denotes the length of a shortest connecting path in

G

, divided by their Euclidean distance. In this paper we study the spectrum of the dilation, over all pairs of vertices of

G

. For paths, trees, and cycles in 2D we present

O

(

n

3/2 + ε

) randomized algorithms that compute, for a given value

κ

≥ 1, the exact number of vertex pairs of dilation >

κ

. Then we present deterministic algorithms that approximate the number of vertex pairs of dilation >

κ

up to an 1+

η

factor. They run in time

O

(

n

log

2

n

) for chains and cycles, and in time

O

(

n

log

3

n

) for trees, in any constant dimension.

We explore the complexity of computing tilings of orthogonal polygons using colored dominoes. A colored domino is a rotatable 2 × 1 rectangle that is partitioned into two unit squares, which are called faces, each of which is assigned a color. In a colored domino tiling of an orthogonal polygon

P

, a set of dominoes completely covers

P

such that no dominoes overlap and so that adjacent faces have the same color. We describe an

O

(

n

) time algorithm for computing a colored domino tiling of a simple orthogonal polygon, where

n

is the number of dominoes used in the tiling. We also show that deciding whether or not a non-simple orthogonal polygon can be tiled with colored dominoes is NP-complete.

We present linear-time algorithms for a pair of robots to travel inside a simple polygon on paths of total minimum length while maintaining visibility with one another. We show that the optimal paths for this mutually visible constraint are almost always each agent’s shortest path. The this may not happen only on a sub-case of when the line of visibility of the source points crosses the line of visibility of the target points. We also show that the travel schedule is computable, but that it also suffers from a pathological case.

Given two compact convex sets

C

1

and

C

2

in the plane, we consider the problem of finding a placement

ϕC

1

of

C

1

that minimizes the area of the convex hull of

ϕC

1

 ∪ 

C

2

. We first consider the case where

ϕC

1

and

C

2

are allowed to intersect (as in “stacking” two flat objects in a convex box), and then add the restriction that their interior has to remain disjoint (as when “bundling” two convex objects together into a tight bundle). In both cases, we consider both the case where we are allowed to reorient

C

1

, and where the orientation is fixed. In the case without reorientations, we achieve exact near-linear time algorithms, in the case with reorientations we compute a (1 + 

ε

)-approximation in time

O

(

ε

− 1/2

log

n

 + 

ε

− 3/2

log

ε

− 1/2

), if two sets are convex polygons with

n

vertices in total.

We consider

variations

of the standard orthogonal range searching motivated by applications in database querying and VLSI layout processing. In a generic instance of such a problem, called a

range-aggregate query

problem we wish to preprocess a set

S

of geometric objects such that given a query orthogonal range

q

, a certain intersection or proximity query on the objects of

S

intersected by

q

can be answered efficiently. Efficient solutions are provided for point enclosure queries, 1-d interval intersection, 2-d orthogonal segment intersection and 1- and 2-d closest pair problems in this framework. Although range-aggregate queries have been widely investigated in the past for aggregation functions like average, count, min, max, sum etc. we consider geometric aggregation operations in this paper.

We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowed in preference lists. This problem is NP-hard and the current best known approximation algorithm achieves the approximation ratio

$2 - c{{\rm log N} \over {N}}$

, where

c

is an arbitrary positive constant and

N

is the number of men in an input. In this paper, we improve the ratio to

$2 - c{{1} \over {\sqrt{N}}}$

, where

c

is a constant such that

$c \leq {{1}\over{4\sqrt{6}}}$

.

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most

g

of them (

g

being the

grooming factor

) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADM’s, one at each endpoint, and in case

g

lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving

g

– 1 ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for

g

= 1 and for a general

g

. Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for

g

= 1. We present an approximation algorithm for this problem. For every value of

g

the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies – including the ring topology – is shown to be 2 ln

g

+

o

(ln

g

). This is the first approximation algorithm for the grooming problem with a general grooming factor

g

.

In this paper we study the scheduling problem of minimizing makespan on identical parallel machines with time-dependent processing times. We first consider the problem with time-dependent processing times on two identical machines to minimize makespan, which is NP-hard. We give a fully polynomial-time approximation scheme for the problem. Furthermore, we generalize the result to the case with

m

machines.

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph

G

= (

V

,

E

) with

n

vertices with a color (or label) function

L

:

E

→ {

c

1

,...,

c

q

}, the labeled maximum matching problem consists in finding a maximum matching on

G

that uses a minimum or a maximum number of colors.

Given a tree

T

=(

V

,

E

) of

n

vertices such that each node

v

is associated with a

value-weight pair

(

val

v

,

w

v

), where

valueval

v

is a real number and

weightw

v

is a non-negative integer, the

density

of

T

is defined as

${\sum_{v \in V^{val_{v}}}} \over {\sum_{v \in V^{w_{v}}}}$

. A

subtree

of

T

is a connected subgraph (

V

′,

E

′) of

T

, where

V

′ ⊆ 

V

and

E

′ ⊆ 

E

. Given two integers

w

min

and

w

max

, the

weight-constrained maximum-density subtree problem

on

T

is to find a maximum-density subtree

T

′ = (

V

′,

E

′) satisfying

$w_{min}{\leq} \Sigma_{v\in V^{\prime}}{w_{v}}{\leq} {w_{max}}$

. In this paper, we first present an

O

(

w

max

n

)-time algorithm to find a weight-constrained maximum-density path in a tree, and then present an

O

(

w

max

2

n

)-time algorithm to find a weight-constrained maximum-density subtree in a tree. Finally, given a node subset

S

⊂

V

, we also present an

O

(

w

max

2

n

)-time algorithm to find a weight-constrained maximum-density subtree of

T

which covers all the nodes in

S

.

Given a number

α

with 0 <

α

< 1, a network

G

= (

V

,

E

) and two nodes

s

and

t

in

G

, we consider the problem of finding two disjoint paths

P

1

and

P

2

from

s

to

t

such that

length

(

P

1) ≤

length

(

P

2

) and

length

(

P

1

) + 

α

·

length

(

P

2

) is minimized. The paths may be node-disjoint or edge-disjoint, and the network may be directed or undirected. This problem has applications in reliable communication. We prove an approximation ratio

${1+\alpha} \over {2\alpha}$

for all four versions of this problem, and also show that this ratio cannot be improved for the two directed versions unless P = NP. We also present Integer Linear Programming formulations for all four versions of this problem. For a special case of this problem, we give a polynomial-time algorithm for finding optimal solutions.

We present a deterministic algorithm for computing the

sensitivity

of a minimum spanning tree or shortest path tree in

O

(

m

log

α

(

m

,

n

)) time, where

α

is the inverse-Ackermann function. This improves upon a long standing bound of

O

(

mα

(

m

,

n

)) established by Tarjan. Our algorithms are based on an efficient

split-findmin

data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity.

Layered multicast is a scalable solution to data dissemination in heterogeneous networks such as the Internet. In this paper, we study the scheduling problem arising in the layered multicast context. Our goal is to generate a multicast schedule for two different objectives, i.e., to minimize the weighted sum (the

L

1

objective) of the per-layer average waiting time, and to minimize the maximum approximation ratio (the

L

 ∞ 

objective) of the subschedules on individual layers. Compared to the previous work on multicast scheduling, this paper addresses the data popularity and the interaction among layers simultaneously. We present a simple randomized algorithm for both objectives of the layered multicast scheduling problem. For the

L

1

objective, we provide a deterministic 2-approximation algorithm for the general multi-layer cases. For the

L

 ∞ 

objective, we present an algorithm for the two-layer case which is 1.6875-approximation ignoring an additive constant.

We describe a fixed parameter algorithm for computing the minimum weight triangulation (MWT) of a simple polygon with (

n

–

k

) vertices on the perimeter and

k

hole vertices in the interior, that is, for a total of

n

vertices. Our algorithm is based on cutting out empty triangles (that is, triangles not containing any holes) from the polygon and processing the parts or the rest of the polygon recursively. We show that with our algorithm a minimum weight triangulation can be found in time at most

O

(

n

3

k

!

k

), and thus in

O

(

n

3

) if

k

is constant. We also note that

k

! can actually be replaced by

b

k

for some constant

b

. We implemented our algorithm in Java and report experiments backing our analysis.

We introduce the concept of multi-directional width-bounded geometric separator and get improved separator for the grid graph, which improves exact algorithm for the protein folding problem in the HP-model. For a grid graph

G

with

n

grid points

P

, there exists a separator

A

 ⊆ 

P

such that

A

has less than or equal to 1.02074

$\sqrt{n}$

points, and

G

–

A

has two disconnected subgraphs with less than or equal to

${2 \over 3}n$

nodes on each of them. We also derive 0.7555

$\sqrt{n}$

lower bound for such a separator on grid graph. The previous upper bound record for the grid graph

$2 \over 3$

-separator is 1.129

$\sqrt{n}$

[6].

Transportation networks model facilities for fast movement on the plane. A transportation network, together with its underlying distance, induces a new distance. Previously, only the Euclidean and the

L

1

distances have been considered as such underlying distances. However, this paper first considers distances induced by general distances and transportation networks, and present a unifying approach to compute Voronoi diagrams under such a general setting. With this approach, we show that an algorithm for convex distances can be easily obtained.

The Earth Mover’s Distance (EMD) on weighted point sets is a distance measure with many applications. Since there are no known exact algorithms to compute the minimum EMD under transformations, it is useful to estimate the minimum EMD under various classes of transformations. For weighted point sets in the plane, we will show a 2-approximation algorithm for translations, a 4-approximation algorithm for rigid motions and an 8-approximation algorithm for similarity transformations. The runtime for translations is

O

(

T

EMD

(

n

,

m

)), the runtime of the latter two algorithms is

O

(

nmT

EMD

(

n

,

m

)), where

T

EMD

(

n

,

m

) is the time to compute the EMD between two fixed weighted point sets with

n

and

m

points, respectively. All these algorithms are based on a more general structure, namely on reference points. This leads to elegant generalizations to higher dimensions. We give a comprehensive discussion of reference points for weighted point sets with respect to the EMD.

In this paper we study the

k

-means clustering problem. It is well-known that the general version of this problem is

$\mathcal{NP}$

-hard. Numerous approximation algorithms have been proposed for this problem. In this paper, we proposed three constant approximation algorithms for

k

-means clustering. The first algorithm runs in time

$O(({{k}\over{\epsilon}})^{k}nd)$

, where

k

is the number of clusters,

n

is the size of input points,

d

is dimension of attributes. The second algorithm runs in time

O

(

k

3

n

2

log

n

). This is the first algorithm for

k

-means clustering that runs in time polynomial in

n

,

k

and

d

. The run time of the third algorithm (

O

(

k

5

log

3

kd

)) is independent of

n

. Though an algorithm whose run time is independent of

n

is known for the

k

-median problem, ours is the first such algorithm for the

k

-means problem.

We address the problem of packing of a set of

n

weighted rectangles into a single rectangle so that the total weight of the packed rectangles is maximized. We consider the case of large resources, that is, the single rectangle is

${\it \Omega}(1/\varepsilon^{3})$

times larger than any rectangle to be packed, for small

ε

> 0. We present an algorithm which finds a packing of a subset of rectangles with the total weight at least (1 − 

ε

) times the optimum. The running time of the algorithm is polynomial in

n

and 1/

ε

. As an application we present a (2 + 

ε

)-approximation algorithm for a special case of the advertisement placement problem.

In this paper, we study the global routing problem in VLSI design and the multicast routing problem in communication networks. We first propose new and realistic models for both problems. Both problems are

$\mathcal{NP}$

-hard. We present the integer programming formulation of both problems and solve the linear programming (LP) relaxations approximately by the fast approximation algorithms for min-max resource-sharing problems in [10]. For the global routing problem, we investigate particular properties of lattice graphs and propose a combinatorial technique to overcome the hardness due to the bend-dependent vertex cost. Finally we develop asymptotic approximation algorithms for both problems depending on the best known approximation ratio for the minimum Steiner tree problem. They are the first known theoretical approximation bound results for these problems.

The Capacitated Traveling Salesman Problem with Pickups and Deliveries (CTSP-PD)[1] can be defined on an undirected graph

T

=(

V

,

E

), where

V

is a set of

n

vertices and

E

is a set of edges. A nonnegative weight

d

(

e

) is associated with each edge

e

∈

E

to indicate its length. Each vertex is either a pickup point, a delivery point, or a transient point. At each pickup point is a load of unit size that can be shipped to any delivery point which requests a load of unit size. Hence we can use

a

(

v

)=1,0,–1 to indicate

v

to be a pickup, a transient, or a delivery point, and

a

(

v

) is referred to as the volume of

v

. The total volumes for pickups and for deliveries are usually assumed to be balanced, i.e.,

$\sum_{v\in {\it V}}{\it a}({\it v})=0$

, which implies that all loads in pickup points must be shipped to delivery points [1]. Among

V

, one particular vertex

r

∈

V

is designated as a depot, at which a vehicle of limited capacity of

k

≥ 1 starts and ends. The problem aims to determine a minimum length feasible route that picks up and delivers all loads without violating the vehicle capacity.

A graph

G

is

δ

-hyperbolic if for any four vertices

u

,

v

,

x

,

y

of

G

the two larger of the three distance sums

d

G

(

u

,

v

) +

d

G

(

x

,

y

),

d

G

(

u

,

x

) +

d

G

(

v

,

y

),

d

G

(

u

,

y

) +

d

G

(

v

,

x

) differ by at most

δ

, and the smallest

δ

≥ 0 for which

G

is

δ

-hyperbolic is called the hyperbolicity of

G

.

In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of

G

can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of

O

(log

2

n

) bits for bounded hyperbolicity graphs with

n

vertices such that distances can be approximated within an additive error of

O

(log

n

). The label length is optimal for every additive error up to

n

ε

. We also show a lower bound of Ω(log log

n

) on the approximation factor, namely every

s

-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires

s

= Ω(log log

n

).

We consider generalizations of the

k

-source sum of vertex eccentricity problem (

k

-SVET) and the

k

-source sum of source eccentricity problem (

k

-SSET) [1], which we call SDET and SSET, respectively, and provide efficient algorithms for their solution. The SDET (SSET, resp.) problem is defined as follows: given a weighted graph

G

and sets

S

of source nodes and

D

of destination nodes, which are subsets of the vertex set of

G

, construct a tree-subgraph

T

of

G

which connects all sources and destinations and minimizes the SDET cost function

$\sum_{d\in {\it D}}{\it max}_{s \in {\it S}}{\it d}_{T}({\it s},{\it d})$

(the SSET cost function

$\sum_{s\in {\it S}}{\rm max}_{d \in {\it D}}{\it d}_{T}({\it s},{\it d})$

, respectively). We describe an

O

(

nm

log

n

)-time algorithm for the SDET problem and thus, by symmetry, to the SSET problem, where

n

and

m

are the numbers of vertices and edges in

G

. The algorithm introduces efficient ways to identify candidates for the sought tree and to narrow down their number to

O

(

m

). Our algorithm readily implies

O

(

nm

log

n

)-time algorithms for the

k

-SVET and

k

-SSET problems as well.

Twisted cubes are attractive alternatives to hypercubes. In this paper, we study a stronger pancyclicity of twisted cubes. We prove that the

n

-dimensional twisted cube is edge-pancyclic for

n

≥ 3. That is, for any (

x

,

y

) ∈

E

(

TQ

n

) (

n

≥ 3) and any integer

l

with 4 ≤

l

≤ 2

n

, a cycle

C

of length

l

can be embedded with dilation 1 into

TQ

n

such that (

x

,

y

) is in

C

. It is clear that an edge-pancyclic graph is also a node-pancyclic graph. Therefore,

TQ

n

is also a node-pancyclic graph for

n

≥ 3.

This work draws attention to combinatorial network abstraction problems which are specified by a class

$\mathcal{P}$

of pattern graphs and a real-valued similarity measure

$\varrho$

based on certain graph properties. For fixed

$\mathcal{P}$

and

$\varrho$

, the optimization task on any graph

G

is to find a subgraph

G

′ which belongs to

$\mathcal{P}$

and minimizes

$\varrho(G,G^{\prime})$

. We consider this problem for the natural case of trees and distance-based similarity measures. In particular, we systematically study spanning trees of graphs that minimize distances, approximate distances, and approximate closeness-centrality with respect to some standard vector and matrix norms. The complexity analysis shows that all considered variants of the problem are NP-complete, except for the case of distance-minimization with respect to the

L

 ∞ 

norm. We further show that unless P = NP, there exist no polynomial-time constant-factor approximation algorithms for the distance-approximation problems if a subset of edges can be forced into the spanning tree.

We present linear-time algorithms for drawing phylogenetic trees in radial and circular representations. In radial drawings given edge lengths (representing evolutionary distances) are preserved, but labels (names of taxons represented in the leaves) need to be adjusted, whereas in circular drawings labels are perfectly spread out, but edge lengths adjusted. Our algorithms produce drawings that are unique solutions to reasonable criteria and assign to each subtree a wedge of its own. The linear running time is particularly interesting in the circular case, because our approach is a special case of Tutte’s barycentric layout algorithm involving the solution of a system of linear equations.

We show that every comparability graph of any two-dimensional poset over

n

elements (a.k.a. permutation graph) can be preprocessed in

O

(

n

) time, if two linear extensions of the poset are given, to produce an

O

(

n

) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of

O

(log

n

) bits so that distance queries between any two vertices are answered by inspecting on their labels only. As a byproduct, our data-structure supports all-pair shortest-path queries in

O

(

d

) time for distance-

d

pairs, and so identifies in constant time the first edge along a shortest path between any source and destination. More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets (we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(

n

1/3

) bit labels).

In this paper, the space requirements for the OBDD representation of certain graph classes, specifically cographs, several types of graphs with few

P

4

s, unit interval graphs, interval graphs and bipartite graphs are investigated. Upper and lower bounds are proven for all these graph classes and it is shown that in most (but not all) cases a representation of the graphs by OBDDs is advantageous with respect to space requirements.

A

compressed full-text self-index

is a data structure that replaces a text and in addition gives indexed access to it, while taking space proportional to the compressed text size. The LZ-index, in particular, requires 4

uH

k

(1+

o

(1)) bits of space, where

u

is the text length in characters and

H

k

is its

k

-th order empirical entropy. Although in practice the LZ-index needs 1.0-1.5 times the text size, its construction requires much more main memory (around 5 times the text size), which limits its applicability to large texts. In this paper we present a practical space-efficient algorithm to construct LZ-index, requiring (4+

ε

)

uH

k

+

o

(

u

) bits of space, for any constant 0 < 

ε

< 1, and

O

(

σu

) time, being

σ

the alphabet size. Our experimental results show that our method is efficient in practice, needing an amount of memory close to that of the final index.

We consider the

Lisw

problem, which is to find the longest increasing subsequences (LIS) in a sliding window of fixed-size w over a sequence

π

1

π

2

...

π

n

. Formally, it is to find a LIS for every window in a set

S

FIX

={

π

〈

i

 + 1,

i

 + 

w

〉|0 ≤ 

i

 ≤ 

n

 − 

w

} ∪ {

π

〈1,

i

〉,

π

〈

n

 − 

i

,

n

〉|

i

 < 

w

}, where a window

π

〈

l

,

r

〉 is a subsequence

π

l

π

l

 + 1

...

π

r

. By maintaining a

canonical antichain partition

in windows, we present an optimal

output-sensitive

algorithm to solve this problem in

O

(

output

) time, where

output

is the sum of the length of the

n

+

w

–1 longest increasing subsequences in those windows of

S

FIX

. In addition, we propose a more generalized problem called

Lisset

, which is to find the LIS for every window in a set

S

VAR

containing

variable-size

windows. By applying our algorithm, we provide an efficient solution for

Lisset

problem which is better than the straight forward generalization of classical LIS algorithms. An upper bound of our algorithm on

Lisset

is discussed.

We study Pareto optimal matchings in the context of house allocation problems. We present an

$O(\sqrt{n}m)$

algorithm, based on Gale’s Top Trading Cycles Method, for finding a maximum cardinality Pareto optimal matching, where

n

is the number of agents and

m

is the total length of the preference lists. By contrast, we show that the problem of finding a minimum cardinality Pareto optimal matching is NP-hard, though approximable within a factor of 2. We then show that there exist Pareto optimal matchings of all sizes between a minimum and maximum cardinality Pareto optimal matching. Finally, we introduce the concept of a signature, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching.

The 3-D

static leaf sequencing

(SLS) problem arises in radiation therapy for cancer treatments, aiming to deliver a prescribed radiation dose to a target tumor accurately and efficiently. The treatment time and machine delivery error are two crucial factors of a solution (i.e., a treatment plan) for the SLS problem. In this paper, we prove that the 3-D SLS problem is NP-hard, and present the first ever algorithm for the 3-D SLS problem that can determine a tradeoff between the treatment time and machine delivery error (also called the “tongue-and-groove” error in medical literature). Our new 3-D SLS algorithm with error control gives the users (e.g., physicians) the option of specifying a machine delivery error bound, and subject to the given error bound, the algorithm computes a treatment plan with the minimum treatment time. We formulate the SLS problem with error control as computing a

k

-weight shortest path in a directed graph and build the graph by computing

g

-matchings and minimum cost flows. Further, we extend our 3-D SLS algorithm to the popular radiotherapy machine models with different constraints. In our extensions, we model the SLS problems for some of the radiotherapy systems as computing a minimum

g

-path cover of a directed acyclic graph. We implemented our new 3-D SLS algorithm suite and conducted an extensive comparison study with commercial planning systems and well-known algorithms in medical literature. Some of our experimental results based on real medical data are presented.