Algorithms and Computation

We present a new overlay, called the

Deterministic Decentralized tree

(

D

2

-tree). The

D

2

-tree compares favourably to other overlays for the following reasons: (a) it provides matching and better complexities, which are deterministic for the supported operations; (b) the management of nodes (peers) and elements are completely decoupled from each other; and (c) an efficient deterministic load-balancing mechanism is presented for the uniform distribution of elements into nodes, while at the same time probabilistic optimal bounds are provided for the congestion of operations at the nodes.

In this paper, we study the following three variants of the classical text indexing problem over small alphabets: the positional pattern matching problem, the position-restricted pattern matching problem, and the indexing version of the variable-length don’t care pattern matching problem. Let

n

be the length of the text,

p

be the length of a query pattern, and Σ be the alphabet. Assume that |Σ| = 

O

(polylog(

n

)). For the first and third problems, we present

O

(

n

)-word indexes with

O

(

p

) query time. For the second problem, we show that each query can be answered in

O

(

n

log

ε

n

) space and

O

(

p

 + 

occ

) time, or in

O

(

n

) space and

O

(

p

 + 

occ

log

ε

n

) time, where

occ

is the number of outputs. When the alphabet size is

O

(polylog(

n

)), the indexes presented in this paper improve the results in [6, 10, 11, 22].

In this paper we describe a dynamic external memory data structure that supports range reporting queries in three dimensions in

$O(\log_B^2 N + \frac{k}{B})$

I/O operations, where

k

is the number of points in the answer and

B

is the block size. Our data structure uses

$O(\frac{N}{B}\log^2_2 N \log^2_2 B)$

blocks of space and supports updates in

$O(\log^3_2 N)$

amortized I/Os. This is the first dynamic data structure that answers three-dimensional range reporting queries in

$\log_B^{O(1)} N + O(\frac{k}{B})$

I/Os.

In this paper we present an implicit dictionary with the working set property i.e. a dictionary supporting

insert

(

e

),

delete

(

x

) and

predecessor

(

x

) in

${\mathcal O}(\log n)$

time and

search

(

x

) in

${\mathcal O}(\log\ell)$

time, where

n

is the number of elements stored in the dictionary and ℓ is the number of distinct elements searched for since the element with key

x

was last searched for. The dictionary stores the elements in an array of size

n

using

no

additional space. In the cache-oblivious model the operations

insert

(

e

),

delete

(

x

) and

predecessor

(

x

) cause

${\mathcal O}(\log_B n)$

cache-misses and

search

(

x

) causes

${\mathcal O}(\log_B \ell)$

cache-misses.

A (

p

,

q

)-total labeling of a graph

G

is an assignment

f

from the vertex set

V

(

G

) and the edge set

E

(

G

) to the set of nonnegative integers such that |

f

(

x

) − 

f

(

y

)| ≥ 

p

if

x

is a vertex and

y

is an edge incident to

x

, and |

f

(

x

) − 

f

(

y

)| ≥ 

q

if

x

and

y

are a pair of adjacent vertices or a pair of adjacent edges, for all

x

and

y

in

V

(

G

) ∪ 

E

(

G

). A

k

-(

p

,

q

)-total labeling is a (

p

,

q

)-total labeling

f

:

V

(

G

) ∪ 

E

(

G

)→{0,...,

k

}, and the (

p

,

q

)-total labeling problem asks the minimum

k

, which we denote by

$\lambda^T_{p,q}(G)$

, among all possible assignments. In this paper, we first give new upper and lower bounds on

$\lambda^T_{p,q}(G)$

for some classes of graphs

G

, in particular, tight bounds on

$\lambda^T_{p,q}(T)$

for trees

T

. We then show that if

p

 ≤ 3

q

/2, the problem for trees

T

is linearly solvable, and give a complete characterization of trees achieving

$\lambda^T_{p,q}(T)$

if in addition Δ ≥ 4 holds, where Δ is the maximum degree of

T

. It is contrasting to the fact that the

L

(

p

,

q

)-labeling problem, which is a generalization of the (

p

,

q

)-total labeling problem, is NP-hard for any two positive integers

p

and

q

such that

q

is not a divisor of

p

.

We introduce and study (1 + 

ε

)

-EMST drawings

, i.e. planar straight-line drawings of trees such that, for any fixed

ε

> 0, the distance between any two vertices is at least

$\frac{1}{1 + \varepsilon}$

the length of the longest edge in the path connecting them. (1 + 

ε

)-EMST drawings are good approximations of Euclidean minimum spanning trees. While it is known that only trees with bounded degree have a Euclidean minimum spanning tree realization, we show that every tree

T

has a (1 + 

ε

)-EMST drawing for any given

ε

> 0. We also present drawing algorithms that compute (1 + 

ε

)-EMST drawings of trees with bounded degree in polynomial area. As a byproduct of one of our techniques, we improve the best known area upper bound for Euclidean minimum spanning tree realizations of complete binary trees.

An

orientation

of an undirected graph

G

is a directed graph

D

on

V

(

G

) with exactly one of directed edges (

u

,

v

) and (

v

,

u

) for each pair of vertices

u

and

v

adjacent in

G

. For integer

k

 ≥ 3, we say a directed graph

D

is

k-cyclic

if every edge of

D

belongs to a directed cycle in

D

of length at most

k

. We consider the problem of deciding if a given graph has a

k

-cyclic orientation. We show that this problem is NP-complete for every fixed

k

 ≥ 3 for general graphs and for every fixed

k

 ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with

k

 = 3, which constructs a 3-cyclic orientation when the answer is affirmative.

For graph

G

, let bw(

G

) denote the branchwidth of

G

and gm(

G

) the largest integer

g

such that

G

contains a

g

×

g

grid as a minor. We show that bw(

G

) ≤ 3gm(

G

) + 1 for every planar graph

G

. This is an improvement over the bound bw(

G

) ≤ 4gm(

G

) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3 + 

ε

)-approximation for the former and (2 + 

ε

)-approximation for the latter, where

ε

is an arbitrary positive constant. We also study the tightness of the above bound. A

k

×

h

cylinder, denoted by

C

k

,

h

, is the Cartesian product of a cycle on

k

vertices and a path on

h

vertices. We show that bw(

C

2

h

,

h

) = 2gm(

C

2

h

,

h

) = 2

h

and therefore the coefficient in the above upper bound is within a factor of 3/2 from the best possible.

We study the problem of maximizing the overlap of two convex polytopes under translation in

${\mathbb R}^d$

for some constant

d

 ≥ 3. Let

n

be the number of bounding hyperplanes of the polytopes. We present an algorithm that, for any

ε

> 0, finds an overlap at least the optimum minus

ε

and reports a translation realizing it. The running time is

$O(n^{{\lfloor d/2 \rfloor}+1} \log^d n)$

with probability at least 1 − 

n

− 

O

(1)

, which can be improved to

O

(

n

log

3.5

n

) in

${\mathbb R}^3$

. The time complexity analysis depends on a bounded incidence condition that we enforce with probability one by randomly perturbing the input polytopes. This causes an additive error

ε

, which can be made arbitrarily small by decreasing the perturbation magnitude. Our algorithm in fact computes the maximum overlap of the perturbed polytopes. All bounds and their big-

O

constants are independent of

ε

.

Let

P

be a path between two points

s

and

t

in a polygonal subdivision

$\mathcal T$

with obstacles and weighted regions. Given a relative error tolerance

ε

 ∈ (0,1), we present the first algorithm to compute a path between

s

and

t

that can be deformed to

P

without passing over any obstacle and the path cost is within a factor 1 + 

ε

of the optimum. The running time is

$O(\frac{h^3}{\varepsilon^2}kn\,\mathrm{polylog}(k,n,\frac{1}{\varepsilon}))$

, where

k

is the number of segments in

P

and

h

and

n

are the numbers of obstacles and vertices in

$\mathcal T$

, respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

The spanning ratio and maximum detour of a graph

G

embedded in a metric space measure how well

G

approximates the minimum complete graph containing

G

and metric space, respectively. In this paper we show that computing the spanning ratio of a rectilinear path

P

in

L

1

space has a lower bound of Ω(

n

log

n

) in the algebraic computation tree model and describe a deterministic

O

(

n

log

2

n

) time algorithm. On the other hand, we give a deterministic

O

(

n

log

2

n

) time algorithm for computing the maximum detour of a rectilinear path

P

in

L

1

space and obtain an

O

(

n

) time algorithm when

P

is a monotone rectilinear path.

We consider the problem of coloring edges of a graph subject to the following constraint: for every vertex

v

, all the edges incident to

v

have to be colored with at most

q

colors. The goal is to find a coloring satisfying the above constraint and using the maximum number of colors.

This problem has been studied in the past from the combinatorial and algorithmic point of view. The optimal coloring is known for some special classes of graphs. There is also an approximation algorithm for general graphs, which in the case

q

 = 2 gives a 2-approximation. However, the complexity of finding the optimal coloring was not known.

We prove that for any integer

q

 ≥ 2 the problem is NP-Hard and APX-Hard. We also present a 5/3-approximation algorithm for

q

 = 2 for graphs with a perfect matching.

Determining the complexity of the colouring problem on AT-free graphs is one of long-standing open problems in algorithmic graph theory. One of the reasons behind this is that AT-free graphs are not necessarily perfect unlike many popular subclasses of AT-free graphs such as interval graphs or co-comparability graphs. In this paper, we resolve the smallest open case of this problem, and present a polynomial time algorithm for 3-colouring of AT-free graphs.

The ℓ-

Coloring

problem is the problem to decide whether a graph can be colored with at most ℓ colors. Let

P

k

denote the path on

k

vertices and

G

 + 

H

and 2

H

the disjoint union of two graphs

G

and

H

or two copies of

H

, respectively. We solve a known open problem by showing that 3-

Coloring

is polynomial-time solvable for the class of graphs with no induced 2

P

3

. This implies that the complexity of 3-

Coloring

for graphs with no induced graph

H

is now classified for any fixed graph

H

on at most 6 vertices. The

Vertex Coloring

problem is the problem to determine the chromatic number of a graph. We show that

Vertex Coloring

is polynomial-time solvable for the class of triangle-free graphs with no induced 2

P

3

and for the class of triangle-free graphs with no induced

P

2

 + 

P

4

. This solves two open problems of Dabrowski, Lozin, Raman and Ries and implies that the complexity of

Vertex Coloring

for triangle-free graphs with no induced graph

H

is now classified for any fixed graph

H

on at most 6 vertices. Our proof technique for the case

H

 = 2

P

3

is based on a novel structural result on the existence of small dominating sets in 2

P

3

-free graphs that admit a

k

-coloring for some fixed

k

.

In the

Maximum Interval Constrained Coloring

problem, we are given a set of intervals on a line and a

k

-dimensional requirement vector for each interval, specifying how many vertices of each of

k

colors should appear in the interval. The objective is to color the vertices of the line with

k

colors so as to maximize the total weight of intervals for which the requirement is satisfied. This

$\mathcal{NP}$

-hard combinatorial problem arises in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. For constant

k

, we give a factor

$O(\sqrt{|{\textsc{Opt}}|})$

-approximation algorithm, where

Opt

is the

smallest-cardinality

maximum-weight solution. We show further that, even for

k

 = 2, the problem remains APX-hard.

The problem

Constrained Longest Common Subsequence

is a natural extension to the classical problem

Longest Common Subsequence

, and has important applications to bioinformatics. Given

k

input sequences

A

1

,...,

A

k

and

l

constraint sequences

B

1

,...,

B

l

, C-LCS(

k

,

l

) is the problem of finding a longest common subsequence of

A

1

,...,

A

k

that is also a common supersequence of

B

1

,...,

B

l

. Gotthilf et al. gave a polynomial-time algorithm that approximates C-LCS(

k

,1) within a factor

$\sqrt{\hat m |\Sigma|}$

, where

$\hat m$

is the length of the shortest input sequence and |Σ| is the alphabet size. They asked whether there are better approximation algorithms and whether there exists a lower bound. In this paper, we answer their questions by showing that their approximation factor

$\sqrt{\hat m |\Sigma|}$

is in fact already very close to optimal although a small improvement is still possible:

1

For any computable function

f

and any

ε

> 0, there is no polynomial-time algorithm that approximates C-LCS

k

,1 within a factor

$f(|\Sigma|)\cdot \hat m^{1/2-\epsilon}$

unless NP = P. Moreover, this holds even if the constraint sequence is unary.

2

There is a polynomial-time randomized algorithm that approximates C-LCS (

k

,1) within a factor

$|\Sigma| \cdot O(\sqrt{{\rm OPT}\cdot\log\log{\rm OPT}/\log{\rm OPT}})$

with high probability, where OPT is the length of the optimal solution,

${\rm OPT} \le \hat m$

.

For the problem over an alphabet of arbitrary size, we show that

3.

For any

ε

> 0, there is no polynomial-time algorithm that approximates C-LCS(

k

,1) within a factor

$\hat m^{1-\epsilon}$

unless NP = SP.

4.

There is a polynomial-time algorithm that approximates C-LCS(

k

, 1) within a factor

$O(\hat m/\log\hat m)$

.

We also present some complementary results on exact and parameterized algorithms for C-LCS(

k

,

l

).

In this paper we investigate approximation algorithms for the multi-vehicle scheduling problem (MVSP). In MVSP we are given a graph

G

 = (

V

,

E

), where each vertex

u

of

V

is associated with a job

j

(

u

), and each edge

e

has a non-negative weight

w

(

e

). There are

m

identical vehicles available to service the jobs. Each job

j

(

u

) has its own release time

r

(

u

) and handling time

h

(

u

). A job

j

(

u

) can only be serviced by one vehicle after its release time

r

(

u

), and the handling time

h

(

u

) represents the time needed to finish processing

j

(

u

). The objective is to find a schedule in which the maximum completion time of the jobs, i.e. the makespan, is minimized. In this paper we present a 3-approximation algorithm for MVSP on trees, and a (

$5-\frac{2}{m}$

)-approximation algorithm for MVSP on general graphs.

In the general search problem we want to identify a specific element using a set of allowed tests. The general goal is to minimize the number of tests performed, although different measures are used to capture this goal. In this work we introduce a novel greedy approach that achieves the best known approximation ratios simultaneously for many different variations of this identification problem. In addition to this flexibility, our algorithm admits much shorter and simpler analyses than previous greedy strategies. As a second contribution, we investigate the potential of greedy algorithms for the more restricted problem of identifying elements of partially ordered sets by comparison with other elements. We prove that the latter problem is as hard to approximate as the general identification problem. As a positive result, we show that a natural greedy strategy achieves an approximation ratio of 2 for tree-like posets, improving upon the previously best known 14-approximation for this problem.

We study the single-device Dynamic Storage Allocation (DSA) problem and multi-device Balancing DSA problem in this paper. The goal is to dynamically allocate the job into memory to minimize the usage of space without concurrency. The SRF problem is just a variant of DSA problem. Our results are as follows,

The NP-completeness for 2-SRF problem, 3-DSA problem, and DSA problem for jobs with agreeable deadlines.

An improved 3-competitive algorithm for jobs with agreeable deadlines on single-device DSA problem. A 4-competitive algorithm for jobs with agreeable deadlines on multi-device Balancing DSA problem.

Lower bounds for jobs with agreeable deadlines: any non-clairvoyant algorithm cannot be (2 − 

ε

)-competitive and any clairvoyant algorithm cannot be (1.54 − 

ε

)-competitive.

The first

O

(log

L

)-competitive algorithm for general jobs on multi-device Balancing DSA problem without any assumption.

Given a set

S

of weighted points in the plane, we consider two problems dealing with planar lines in ℝ

2

under the weighted Euclidean distance: (1) Preprocess

S

into a data structure that efficiently finds a nearest point among

S

of a query “line”. (2) Find an optimal “line” that maximizes the minimum of the weighted distance to any point of

S

. We introduce a unified approach to both problems based on a new geometric transformation that maps lines in the plane into points in a line space. It turns out that our transformation, together with its target space, well describes the proximity relations between given weighted points

S

and every planar line in ℝ

2

. We define a Voronoi-like tessellation on the line space and investigate its geometric, combinatorial, and computational properties. As its applications, we obtain several new results on the two problems.

In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items, respectively) arrive over time, which must be packed into square bins of size 1×1. 90°-rotation of an item is allowed. When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items. The objective is to minimize the total number of bins used for packing all the items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened.

Our contributions are as follows: For 1-space bounded 2-dimensional bin packing, we propose an online packing strategy with competitive ratio 5.155, surpassing the previous 8.84-competitive bound. The lower bound of competitive ratio is also improved from 2.5 to 3. Furthermore, we study 1-space bounded square packing, which is a special case of the bin packing problem. We give a 4.5-competitive packing algorithm, and prove that the lower bound of competitive ratio is at least 8/3.

In the (discrete) CNN problem, online requests appear as points in ℝ

2

. Each request must be served before the next one is revealed. We have a server that can serve a request simply by aligning either its

x

or

y

coordinate with the request. The goal of the online algorithm is to minimize the total

L

1

distance traveled by the server to serve all the requests. The best known competitive ratio for the discrete version is 879 (due to Sitters and Stougie).

We study the continuous version, in which, the request can move continuously in ℝ

2

and the server must continuously serve the request. A simple adversarial argument shows that the lower bound on the competitive ratio of any online algorithm for the continuous CNN problem is 3. Our main contribution is an online algorithm with competitive ratio

$3+2 \sqrt{3} \approx 6.464$

. Our analysis is tight. The continuous version generalizes the discrete orthogonal CNN problem, in which every request must be

x

or

y

aligned with the previous request. Therefore, our result improves upon the previous best known competitive ratio of 9 for the discrete orthogonal CNN problem (due to Iwama and Yonezawa).

In the periodic packet routing problem each of a set of tasks repeatedly emits packets over an infinite time horizon. These have to be routed along their fixed path through a common network. A schedule must resolve the resource conflicts on the arcs, such that the maximal delay any packet experiences can be bounded. The scheduling policies themselves must be simple enough to be executed in real-time, i.e., with low computational overhead. We compare the potential of two natural classes of policies, namely, template schedules and priority schedules by giving algorithms and lower bounds.

Network flows and scheduling have been studied intensely, but mostly separately. In many applications a joint optimization model for routing and scheduling is desireable. Therefore, we study flows over time with a demand split into jobs. Our objective is to minimize the weighted sum of completion times of these jobs. This is closely related to preemptive scheduling on a single machine with a processing speed increasing over time. For both, flow scheduling and increasing speed scheduling, we provide an EPTAS. Without release dates we can prove a

tight

approximation factor of

$(\sqrt{3}+1)/2$

for Smith’s rule, by fully characterizing the worst case instances. We give exact algorithms for some special cases and a dynamic program for speed functions with a constant number of speeds. We can prove a competitive ratio of 2 for the online version. We also study the class of blind algorithms, i.e., those which schedule without knowledge of the speed function.

Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel platforms. However, with the increasing number of processors, the cost for managing a single centralized list becomes prohibitive. The objective of this work is to study the extra cost that must be paid when the list is distributed among the processors. We present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load unbalance between the local lists. A bound on the deviation from the mean is also derived. Then, we apply this technique to show that the expected makespan for scheduling

W

unit independent tasks on

m

processors is equal to

W

/

m

with an additional term in 3.65log

2

W

. Moreover, simulations show that our bound is very close to the exact value, approximately 50% off. This new analysis also enables to study the influence of the initial repartition of tasks and the reduction of the number of steals when several thieves can simultaneously steal work in the same processor’s list.

We consider the traveling tournament problem, which is a well-known benchmark problem in tournament timetabling. The most important variant of the problem imposes restrictions on the number of consecutive home games or away games a team may have. We consider the case where at most two consecutive home games or away games are allowed. We show that the well-known independent lower bound for this case cannot be reached and present an approximation algorithm that has an approximation ratio of

$3/2+\frac{6}{n-4}$

, where

n

is the number of teams in the tournament. In the case that

n

is divisible by 4, this approximation ratio improves to

$3/2+\frac{5}{n-1}$

.

We present a data structure that stores a string

s

[1..

n

] over the alphabet [1..

σ

] in

nH

0

(

s

) + 

o

(

n

)(

H

0

(

s

) + 1) bits, where

H

0

(

s

) is the zero-order entropy of

s

. This data structure supports the queries

access

and

rank

in time

$({\mathcal O}{{\rm lg lg}\sigma})$

, and the

select

query in constant time. This result improves on previously known data structures using

$nH_0(s)+o(n\lg\sigma)$

bits, where on highly compressible instances the redundancy

$o(n\lg\sigma)$

cease to be negligible compared to the

nH

0

(

s

) bits that encode the data. The technique is based on combining previous results through an ingenious partitioning of the alphabet, and practical enough to be implementable. It applies not only to strings, but also to several other compact data structures. For example, we achieve (

i

) faster search times and lower redundancy for the smallest existing full-text self-index; (

ii

) compressed permutations

π

with times for

π

() and

π

− 1

() improved to log-logarithmic; and (

iii

) the first compressed representation of dynamic collections of disjoint sets.

We give the first

fully compressed

representation of a set of

m

points on an

n

×

n

grid, taking

H

 + 

o

(

H

) bits of space, where

$H=\lg {n^2 \choose m}$

is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with a performance that is comparable to that of uncompressed structures and that improves upon the only previous compressed structure. Operating within entropy-bounded space opens a new line of research on an otherwise well-studied area, and is becoming extremely important for handling large datasets.

We study the problem of identifying palindromes in compressed strings. The underlying compression scheme is called run-length encoding, which has been extensively studied and widely applied in diverse areas. Given a run-length encoded string

$\textsc{rle}(T)$

, we show how to preprocess

$\textsc{rle}(T)$

to support efficient retrieval of the longest palindrome with a specified center position and a tolerated number of mismatches between its two arms. Let

n

be the number of runs of

$\textsc{rle}(T)$

and

k

be the tolerated number of mismatches. We present two algorithms for the problem, both with preprocessing time polynomial in the number of runs. The first algorithm, devised for small

k

, identifies the desired palindrome in

O

(log

n

 + min {

k

,

n

}) time with

O

(

n

log

n

) preprocessing time, while the second algorithm achieves

O

(log

2

n

) query time, independent of

k

, after

O

(

n

2

log

n

)-time preprocessing.

Let

T

be a given tree. Each vertex of

T

is either a supply vertex or a demand vertex, and is assigned a positive integer, called the supply or the demand. Every demand vertex

v

of

T

must be supplied an amount of “power,” equal to the demand of

v

, from exactly one supply vertex through edges in

T

. Each edge

e

of

T

has a direction, and is assigned a positive integer which represents the cost required to delete

e

from

T

or reverse the direction of

e

. Then one wishes to obtain subtrees of

T

by deleting edges and reversing the directions of edges so that (a) each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and (b) each subtree is rooted at the supply vertex in a sense that every edge is directed away from the root. We wish to minimize the total cost to obtain such rooted subtrees from

T

. In the paper, we first show that this minimization problem is NP-hard, and then give a pseudo-polynomial-time algorithm to solve the problem. We finally give a fully polynomial-time approximation scheme (FPTAS) for the problem.

(

t

,

k

)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least

k

faulty processors should be identified and repaired in each iteration provided there are at most

t

faulty processors, where

t

 ≥ 

k

. Let

κ

(

G

) and

n

(

G

) be the node connectivity and the number of nodes in

G

, respectively. We show that the class of

m

-dimensional component-composition graphs

G

for

m

 ≥ 4 is (Ω(

h

),

κ

(

G

))-diagnosable, where

$h=\frac{2^{m-2}\times \lg{(m-1)}}{m-1}$

if 2

m

 − 1

 ≤ 

n

(

G

) < 

m

!; and

h

 = 2

m

 − 2

if

n

(

G

) ≥ 

m

!. Based on this result, the (

t

,

k

)-diagnosability of numerous multiprocessor systems can be computed efficiently.

Given an undirected 3-connected graph

G

with

n

vertices and

m

edges, we modify depth-first search to produce a sparse spanning subgraph with at most 4

n

 − 10 edges that is still 3-connected. If

G

is 2-connected, to maintain 2-connectivity, the resulting graph will have at most 2

n

 − 3 edges. The way depth-first search discards irrelevant edges illustrates the reason behind its ability to verify and certify biconnectivity [1,2,3] and triconnectivity [4,5] in linear time. Dealing with a sparser graph, after the first depth-first-search calls, makes the algorithms in [2,5] more efficient. We also give a characterization of separation pairs of a 2-connected graph in terms of the resulting sparse graph.

In this paper we study the prevalent problem of graph partitioning by analyzing the diffusion-based partitioning heuristic

Bubble

-FOS/C, a key component of the practically successful partitioner

DibaP

[14]. Our analysis reveals that

Bubble

-FOS/C, which yields well-shaped partitions in experiments, computes a relaxed solution to an edge cut minimizing binary quadratic program (BQP). It therefore provides the first substantial theoretical insights (beyond intuition) why

Bubble

-FOS/C (and therefore indirectly

DibaP

) yields good experimental results. Moreover, we show that in bisections computed by

Bubble

-FOS/C, at least one of the two parts is connected. Using arguments based on random walk techniques, we prove that in vertex-transitive graphs actually both parts must be connected components each. All these results may help to eventually bridge the gap between practical and theoretical graph partitioning.

The

Induced Subgraph Isomorphism

problem on two input graphs

G

and

H

is to decide whether

G

has an induced subgraph isomorphic to

H

. Already for the restricted case where

H

is a complete graph the problem is NP-complete, as it is then equivalent to the

Clique

problem. In a recent paper [7] Marx and Schlotter show that

Induced Subgraph Isomorphism

is NP-complete when

G

and

H

are restricted to be interval graphs. They also show that the problem is

W

[1]-hard with this restriction when parametrised by the number of vertices in

H

. In this paper we show that when

G

is an interval graph and

H

is a connected proper interval graph, the problem is solvable in polynomial time. As a more general result, we show that when

G

is an interval graph and

H

is an arbitrary proper interval graph, the problem is fixed parameter tractable when parametrised by the number of connected components of

H

. To complement our results, we prove that the problem remains NP-complete when

G

and

H

are both proper interval graphs and

H

is disconnected.

Two planar graphs

G

1

and

G

2

sharing some vertices and edges are

simultaneously planar

if they have planar drawings such that a shared vertex [edge] is represented by the same point [curve] in both drawings. It is an open problem whether simultaneous planarity can be tested efficiently. We give a linear-time algorithm to test simultaneous planarity when the two graphs share a 2-connected subgraph. Our algorithm extends to the case of

k

planar graphs where each vertex [edge] is either common to all graphs or belongs to exactly one of them.

We consider the problem of computing the discrete Fréchet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension

d

, we present an algorithm for this problem that returns in time

$2^{O(d^2)} m^2n^2\log^2(mn)$

the Fréchet distance lower bound between two imprecise polygonal curves with

n

and

m

vertices, respectively. We give an improved algorithm for the planar case with running time

O

(

mn

log

2

(

mn

) + (

m

2

 + 

n

2

)log(

mn

)). In the

d

-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the

L

 ∞ 

distance, we give an

O

(

dmn

log(

dmn

))-time algorithm.

We also give efficient

O

(

dmn

)-time algorithms to approximate the Fréchet distance upper bound, as well as the smallest possible Fréchet distance lower/upper bound that can be achieved between two imprecise point sequences when one is allowed to translate them. These algorithms achieve constant factor approximation ratios in “realistic” settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size).

We study a generalization of the well known bottleneck spanning tree problem called

Best Case Connectivity with Uncertainty

: Given a family of geometric regions, choose one point per region, such that the length of the longest edge in a spanning tree of a disc intersection graph is minimized. We show that this problem is NP-hard even for very simple scenarios such as line segments and squares. We also give exact and approximation algorithms for the case of line segments and unit discs respectively.

We show that the Yao graph

Y

4

in the

L

2

metric is a spanner with stretch factor

$8\sqrt{2}(29+23\sqrt{2})$

.

In this paper, we introduce the following problem in the theory of algorithmic self-assembly: given an input shape as the seed of a tile-based self-assembly system, design a finite tile set that can, in some sense, uniquely identify whether or not the given input shape–drawn from a very general class of shapes–matches a particular target shape. We first study the complexity of correctly identifying squares. Then we investigate the complexity associated with the identification of a considerably more general class of non-square, hole-free shapes.