Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed conference proceedings of the 9th International Workshop on Algorithms and Computation, WALCOM 2015, held in Dhaka, Bangladesh, in February 2015. The 26 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 85 submissions. The papers are organized in topical sections on approximation algorithms, data structures and algorithms, computational geometry, combinatorial algorithms, distributed and online algorithms, graph drawing and algorithms, combinatorial problems and complexity, and graph enumeration and algorithms.

Inhaltsverzeichnis

Encoding Data Structures

In recent years, there has been an explosion of interest in

succinct

data structures, which store the given data in compact or compressed formats and answer queries on the data rapidly while it is still in its compressed format. Our focus in this talk is to introduce

encoding

data structures. Encoding data structures consider the data together with the queries and aim to store only as much information about the data as is needed to store the queries. Once this is done, the original data can be deleted. In many cases, one can obtain space-efficient encoding data structures even when the original data is incompressible.

Rajeev Raman

Fast Algorithms for Constrained Graph Density Problems

We consider the question of finding communities in

large

social networks. In literature and practice, “communities” refer to a

well-connected

subgraph of the entire network. For instance, the notion of

graph density

has been considered as a reasonable measure of a community. Researchers have also looked at the

minimum degree

of a subgraph as a measure of the connectedness of the community.

Typically, a community is meaningful in the context of a social network if it is of somewhat significant size. Thus, earlier work has considered the densest graph problem subject to various

co-matroid constraints

. Most of these algorithms utilize an exact dense subgraph procedure as a subroutine; such a subroutine involves computing maximum flows or solving LPs. Consequently, they are rather inefficient when considered for massive graphs. For massive graphs, we are constrained to run in near-linear time, while producing subgraphs that provide reasonable approximations to the optimal solutions.

Our current work presents efficient greedy algorithms for the problem of graph density subject to an even more general class of constraints called

upward-monotone

constraints (these subsume co-matroid constraints). This generalizes and extends earlier work significantly. For instance, we are thereby able to present near-linear time 3-factor approximation algorithms for density subject to co-matroid constraints; we are also able to obtain 2-factor LP-based algorithms for density subject to 2 co-matroid constraints.

Our algorithms heavily utilize the

core decomposition

of a graph.

Venkatesan Chakaravarthy, Neelima Gupta, Aditya Pancholi, Sambuddha Roy

The Directed Ring Loading with Penalty Cost

We study the directed ring loading problem with penalty cost, which is to select some of given multicast requests represented by hyperedges with different demands and embed them in a directed ring, such that the sum of the maximum congestion among all links on the ring and the total penalty cost of the unselected multicast requests is minimized. We prove that this problem is

NP

-hard even if the demand is divisible, and then design a 1.582-approximation algorithm for the demand divisible case and a 3-approximation algorithm for the demand indivisible case, respectively. As a consequence, for any

ε

> 0, we present a (1.582 +

ε

)-approximation algorithm for the case where every multicast request contains exactly one sink.

Li Guan, Jianping Li, Xuejie Zhang, Weidong Li

Edge-Colorings of Weighted Graphs

(Extended Abstract)

Let

G

be a graph with a positive integer weight

ω

(

v

) for each vertex

v

. One wishes to assign each edge

e

of

G

a positive integer

f

(

e

) as a color so that

ω

(

v

) ≤ |

f

(

e

) −

f

(

e

)| for any vertex

v

and any two edges

e

and

e

incident to

v

. Such an assignment

f

is called an

ω

-edge-coloring of

G

, and the maximum integer assigned to edges is called the span of

f

. The

ω

-chromatic index of

G

is the minimum span over all

ω

-edge-colorings of

G

. In the paper, we present various upper and lower bounds on the

ω

-chromatic index, and obtain three efficient algorithms to find an

ω

-edge-coloring of a given graph. One of them finds an

ω

-edge-coloring with span smaller than twice the

ω

-chromatic index.

Yuji Obata, Takao Nishizeki

Unit Covering in Color-Spanning Set Model

In this paper, we consider two new variants of the unit covering problem in color-spanning set model: Given a set of

n

points in

d

-dimensional plane colored with

m

colors, the

MinCSBC

problem is to select

m

points of different colors minimizing the minimum number of unit balls needed to cover them. Similarly, the

MaxCSBC

problem is to choose one point of each color to maximize the minimum number of needed unit balls. We show that MinCSBC is NP-hard and hard to approximate within any constant factor even in one dimension. For

d

= 1, however, we propose an ln (

m

)-approximation algorithm and present a constant-factor approximation algorithm for fixed

f

, where

f

is the maximum frequency of the colors. For the MaxCSBC problem, we first prove its NP-hardness. Then we present an approximation algorithm with a factor of 1/2 in one-dimensional case.

Ehsan Emamjomeh-Zadeh, Mohammad Ghodsi, Hamid Homapour, Masoud Seddighin

Compact Encodings and Indexes for the Nearest Larger Neighbor Problem

Given a

d

-dimensional array, for any integer

d

> 0, the

nearest larger value

(

NLV

) query returns the position of the element which is closest, in

L

1

distance, to the query position, and is larger than the element at the query position. We consider the problem of preprocessing a given array, to construct a data structure that can answer

NLV

queries efficiently. In the 2-D case, given an

n

×

n

array

A

, we give an asymptotically optimal

O

(

n

2

)-bit encoding that answers

NLV

queries in

O

(1) time. When

A

is a binary array, we describe a simpler

O

(

n

2

)-bit encoding that also supports

NLV

queries in

O

(1) time. Using this, we obtain an index of size

O

(

n

2

/

c

) bits that supports

NLV

queries in

O

(

c

) time, for any parameter

c

, where 1 ≤

c

≤

n

, matching the lower bound. For the 1-D case we consider the

nearest larger right value

(

NLRV

) problem where the nearest larger value to the right is sought. For an array of length

n

, we obtain an index that takes

O

((

n

/

c

) log

c

) bits, and supports

NLRV

queries in

O

(

c

) time, for any any parameter

c

, where 1 ≤

c

≤

n

, improving the earlier results of Fischer et al. and Jayapaul et al.

Seungbum Jo, Rajeev Raman, Srinivasa Rao Satti

A Practical Succinct Data Structure for Tree-Like Graphs

We present a new succinct data structure for graphs that are “tree-like,” in the sense that the number of “additional” edges (w.r.t. a spanning tree) is not too high. Our algorithmic idea is to represent a BFS-spanning tree of the graph with a succinct data structure for trees, and enhance it with additional information that accounts for the non-tree edges. In practical tests, our data structure performs well for graphs containing up to 10% of non-tree edges, reducing the space of a pointer-based representation by a factor of ≈20, while increasing the worst-case running times for the operations by roughly the same factor.

Johannes Fischer, Daniel Peters

Forming Plurality at Minimum Cost

In this paper, we are concerned with a kind of spatial equilibria, the plurality points, in two-dimensional Euclidean space. Given a set of voters, each of which corresponds to a point, a plurality point is defined as a point closer to at least as many voters as any other point in the space. We generalize the definition by appending weights on the voters, and define the plurality point as a point

$\vartriangle$

satisfying that the sum of weights of the voters closer to

$\vartriangle$

is no less than that of the voters closer to any other point in the space. To remedy the issue of the non-existence of plurality points, we investigate the problem of eliminating some voters with minimum “cost” so that there is a plurality point with respect to the remaining voters. We show that the problem is NP-hard. Moreover, if all voters’ weights are restricted to be equal, we show that the problem can be solved in

O

(

n

5

log

n

) time, where

n

is the number of voters.

Wei-Yin Lin, Yen-Wei Wu, Hung-Lung Wang, Kun-Mao Chao

Approximate Distance Oracle in O(n 2) Time and O(n) Space for Chordal Graphs

We preprocess a given unweighted chordal graph

G

on

n

vertices in

O

(

n

2

) time to build a data structure of

O

(

n

) size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices

u

i

,

u

j

∈

V

(

G

), 1 ≤

i

,

j

≤

n

, we take constant time to output a distance value

d

ij

≤ 2

d

G

(

u

i

,

u

j

) + 8 using our data structure, where

d

G

is the distance between

u

i

and

u

j

in

G

. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in

O

(

n

2.373

) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph.

Gaurav Singh, N. S. Narayanaswamy, G. Ramakrishna

Straight-Path Queries in Trajectory Data

Inspired by sports analysis, we study data structures for storing a trajectory representing the movement of a player during a game, such that the following queries can be answered: Given two positions

s

and

t

, report all sub-trajectories in which the player moved in a more or less straight line from

s

to

t

. We consider two measures of straightness, namely

dilation

and

direction deviation

, and present efficient construction algorithms for our data structures, and analyze their performance.

We also present an

O

(

n

1.5 +

ε

) algorithm that, given a trajectory

P

and a threshold

τ

, finds a simplification of

P

with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory of length at most

τ

times the length of the edge. This significantly improves the fastest known algorithm for the problem.

Mark de Berg, Ali D. Mehrabi

Folding a Paper Strip to Minimize Thickness

In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.

Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno

An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments

(Extended Abstract)

This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set

S

of

n

line segments that may intersect or cross each other. If there are

k

intersections among the input segments in

S

, our algorithm takes

O

(

n

α

(

n

) log

n

+

k

) time, where

α

(·) denotes the functional inverse of the Ackermann function. The best known running time prior to this work was

O

((

n

+

k

) log

n

). Since the lower bound of the problem is shown to be Ω(

n

log

n

+

k

) in the worst case, our algorithm is worst-case optimal for

k

= Ω(

n

α

(

n

) log

n

), and is only a factor of

α

(

n

) away from the lower bound. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.

Sang Won Bae

PTAS’s for Some Metric p-source Communication Spanning Tree Problems

In this work we consider some NP-hard cases of the metric

p

-source communication spanning tree problem (metric

p

-

OCT

). Given an undirected complete graph

G

= (

V

,

E

) with non-negative length

ω

(

e

) associated to each edge

e

∈

E

satisfying the triangular inequality, a set

S

⊆

V

of

p

vertices and non-negative routing requirements

ψ

(

u

,

v

) between all pairs of nodes

u

∈

S

and

v

∈

V

, the metric

p

-

OCT

’s objective is to find a spanning tree

T

of

G

, that minimizes: ∑

u

∈

S

∑

v

∈

V

ψ

(

u

,

v

)

d

(

T

,

u

,

v

), where

d

(

H

,

x

,

y

) is the minimum distance between nodes

x

and

y

in a graph

H

⊆

G

. This problem is a particular case of the optimum communication spanning tree problem (

OCT

). We prove a general result which allows us to derive polynomial approximation schemes for some NP-hard cases of the metric

p

-

OCT

improving the existing ratios for these problems.

Santiago V. Ravelo, Carlos E. Ferreira

Fault-Tolerant Gathering of Asynchronous Oblivious Mobile Robots under One-Axis Agreement

In this paper, we have studied one of the fundamental coordination problems for multi robot system, namely

gathering

, for

n

≥ 2 asynchronous, oblivious mobile robots in the presence of

f

<

n

faulty robots. Earlier works have reported that, in general, to solve gathering problem for asynchronous robots, many assumptions are required, like multiplicity detection or total agreement in coordinate axis or constant amount of memory bits. However, in this paper we have proved that gathering of asynchronous robots is possible with less number of such assumptions and even in the presence of any number of faulty robots. In our case, the robots only agree on the direction and orientation of any one axis.

Subhash Bhagat, Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya

Enumerating Eulerian Trails via Hamiltonian Path Enumeration

Given an undirected graph

G

, we consider enumerating all Eulerian trails, that is, walks containing each of the edges in

G

just once. We consider achieving it with the enumeration of Hamiltonian paths with the

zero-suppressed decision diagram

(ZDD), a data structure that can efficiently store a family of sets satisfying given conditions. First we compute the

line graph

L

(

G

), the graph representing adjacency of the edges in

G

. We also formulated the condition when a Hamiltonian path in

L

(

G

) corresponds to an Eulerian trail in

G

because every trail in

G

corresponds to a path in

L

(

G

) but the converse is not true. Then we enumerate all Hamiltonian paths in

L

(

G

) satisfying the condition with ZDD by representing them as their sets of edges.

Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi, Shin-ichi Minato

The Impact of Communication Patterns on Distributed Self-Adjusting Binary Search Trees

This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the nearly thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided. To do so, the process of self-adjustment is modeled similarly to a basic network creation game in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and convergence is related to certain structures of the communication interests, which we call conflicts. We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well. Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.

Thim Strothmann

An Efficient Silent Self-Stabilizing Algorithm for 1-Maximal Matching in Anonymous Networks

We propose a new self-stabilizing 1-maximal matching algorithm which is

silent

and works for any

anonymous

networks without a cycle of a length of a multiple of 3 under a central

unfair

daemon. Let

n

and

e

be the numbers of nodes and edges in a graph, respectively. The time complexity of the proposed algorithm is

O

(

e

) moves. Therefore, the complexity is

O

(

n

) moves for trees or rings whose length is not a multiple of 3. That is a significant improvement from the best existing results of

O

(

n

4

) moves for the same problem setting.

Yuma Asada, Michiko Inoue

Dynamic Online Multiselection in Internal and External Memory

We consider the dynamic version of the

online multiselection

problem for internal and external memory, in which

q

selection queries are requested on an unsorted array of

N

elements. Our internal memory result is 1-competitive with the offline result of Kaligosiet al.[ICALP 2005]. In particular, we extend the results of Barbaryet al.[ESA 2013] by supporting arbitrary

insertions

and

deletions

while supporting online

select

and

search

queries on the array. Assuming that the insertion of an element is immediately preceded by a search for that element, we show that our dynamic online algorithm performs an optimal number of comparisons, up to lower order terms and an additive

O

(

N

) term.

For the external memory model, we describe the first online multiselection algorithm that is

O

(1)-competitive. This result improves upon the work of Sibeyn [Journal of Algorithms 2006] when

q

>

m

, where

m

is the number of blocks that can be stored in main memory. We also extend it to support searches, insertions, and deletions of elements efficiently.

Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti, Jonathan Sorenson

Competitive Analysis for Multi-objective Online Algorithms

So far, the concept of competitive analysis for online problems is in general applied to single-objective online problems. However, many online problems can be extended to multi-objective online problems in a natural way, but a uniform theory for the analysis of these problems is not provided in the literature. We expand the concept of competitive analysis to multi-objective online problems and achieve a consistent framework for the analysis of multi-objective online problems. Furthermore, we analyze the multi-objective time series search problem and present deterministic algorithms with best possible competitive ratios.

Morten Tiedemann, Jonas Ide, Anita Schöbel

Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends

Given two planar graphs that are defined on the same set of vertices, a

RAC simultaneous drawing

is a drawing of the two graphs where each graph is drawn planar, no two edges overlap, and edges of one graph can cross edges of the other graph only at right angles. In the geometric version of the problem, vertices are drawn as points and edges as straight-line segments. It is known, however, that even pairs of very simple classes of planar graphs (such as wheels and matchings) do not always admit a geometric RAC simultaneous drawing.

In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow edges to have bends. We prove that any pair of planar graphs admits a RAC simultaneous drawing with at most six bends per edge. For more restricted classes of planar graphs (e.g., matchings, paths, cycles, outerplanar graphs, and subhamiltonian graphs), we significantly reduce the required number of bends per edge. All our drawings use quadratic area.

Michael A. Bekos, Thomas C. van Dijk, Philipp Kindermann, Alexander Wolff

An Improved Algorithm for Parameterized Edge Dominating Set Problem

An edge dominating set of a graph

G

= (

V

,

E

) is a subset

M

⊆

E

of edges such that each edge in

E

∖

M

is incident to at least one edge in

M

. In this paper, we consider the parameterized edge dominating set problem which asks us to test whether a given graph has an edge dominating set with size bounded from above by an integer

k

or not, and we design an

O

*

(2.2351

k

)-time and polynomial-space algorithm. This is an improvement over the previous best time bound of

O

*

(2.3147

k

). We also show that a related problem: the parameterized weighted edge dominating set problem can be solved in

O

*

(2.2351

k

) time and polynomial space.

Ken Iwaide, Hiroshi Nagamochi

On Bar (1,j)-Visibility Graphs

(Extended Abstract)

A graph is called a bar (1,

j

)-visibility graph if its vertices can be represented as horizontal vertex-segments (bars) and each edge as a vertical edge-segment connecting the bars of the end vertices such that each edge-segment intersects at most one other bar and each bar is intersected by at most

j

edge-segments. Bar (1,

j

)-visibility refines bar 1-visibility in which there is no bound on the number of intersections of bars.

We construct gadgets which show structural properties of bar (1,

j

)-visibility graphs, study bounds on the maximal number of edges and show that there is an infinite hierarchy of bar (1,

j

)-visibility graphs. Finally, we prove that it is

NP

-complete to test whether a graph is bar (1, ∞ )-visible.

Franz J. Brandenburg, Niklas Heinsohn, Michael Kaufmann, Daniel Neuwirth

Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs

In this paper, we consider the

RedBluePath

problem, which states that given a graph

G

whose edges are colored either red or blue and two fixed vertices

s

and

t

in

G

, is there a path from

s

to

t

in

G

that alternates between red and blue edges. The

RedBluePath

problem in planar DAGs is

NL

-complete. We exhibit a polynomial time and

$O(n^{\frac{1}{2}+\epsilon})$

space algorithm (for any

ε

> 0) for the

RedBluePath

problem in planar DAG. We also consider a natural relaxation of

RedBluePath

problem, denoted as

EvenPath

problem. The

EvenPath

problem in DAGs is known to be

NL

-complete. We provide a polynomial time and

$O(n^{\frac{1}{2}+\epsilon})$

space (for any

ε

> 0) bound for

EvenPath

problem in planar DAGs.

Diptarka Chakraborty, Raghunath Tewari

Non-repetitive Strings over Alphabet Lists

A word is non-repetitive if it does not contain a subword of the form

vv

. Given a list of alphabets

L

=

L

1

,

L

2

,…,

L

n

, we investigate the question of generating non-repetitive words

w

=

w

1

w

2

w

n

, such that the symbol

w

i

is a letter in the alphabet

L

i

. This problem has been studied by several authors (e.g., [GKM10], [Sha09]), and it is a natural extension of the original problem posed and solved by A. Thue. While we do not solve the problem in its full generality, we show that such strings exist over many classes of lists. We also suggest techniques for tackling the problem, ranging from online algorithms, to combinatorics over 0-1 matrices, and to proof complexity. Finally, we show some properties of the extension of the problem to abelian squares.

Neerja Mhaskar, Michael Soltys

Dichotomy Theorems for Homomorphism Polynomials of Graph Classes

In this paper, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiant’s model. We are given a fixed graph

H

and want to find all graphs, from some graph class, homomorphic to this

H

. These graphs will be encoded by a family of polynomials.

We give dichotomies for the polynomials for cycles, cliques, trees, outerplanar graphs, planar graphs and graphs of bounded genus.

Christian Engels

Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid

Common unfolding of a regular tetrahedron and a Johnson-Zalgaller solid is investigated. More precisely, we investigate the sets of all edge unfoldings of Johnson-Zalgaller solids. Among 92 Johnson-Zalgaller solids, some of edge unfolding of J17 and J84 admit to fold into a regular tetrahedron. On the other hand, there are no edge unfolding of the other Johnson-Zalgaller solids that admit to fold into a regular tetrahedron.

Yoshiaki Araki, Takashi Horiyama, Ryuhei Uehara

Threshold Circuits for Global Patterns in 2-Dimensional Maps

In this paper, we consider a biologically-inspired Boolean function, called

$P^n_D$

, which models a task for detecting specific global spatial arrangements of local visual patterns on a 2-dimensional map. We prove that

$P^n_D$

is computable by a threshold circuit of size

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

, which is improvement on the previous upper bound

O

(

n

). We also show that the size of our circuit is almost optimal up to logarithmic factor: we show that any threshold circuit computing

$P^n_D$

needs size

$\Omega(\sqrt{n}/\log n)$

.

Kei Uchizawa, Daiki Yashima, Xiao Zhou

Superset Generation on Decision Diagrams

Generating all supersets from a given set family is important, because it is closely related to identifying cause-effect relationship. This paper presents an efficient method for superset generation by using the compressed data structures BDDs and ZDDs effectively. We analyze the size of a BDD that represents all supersets. As a by-product, we obtain a non-trivial upper bound for the size of a BDD that represents a monotone Boolean function in a fixed variable ordering.

Takahisa Toda, Shogo Takeuchi, Koji Tsuda, Shin-ichi Minato

On Triangle Cover Contact Graphs

Let

S

= {

p

1

,

p

2

,…,

p

n

} be a set of pairwise disjoint geometric objects of some type in a 2

D

plane and let

C

= {

c

1

,

c

2

,…,

c

n

} be a set of closed objects of some type in the same plane with the property that each element in

C

covers exactly one element in

S

and any two elements in

C

are interior-disjoint. We call an element in

S

a

seed

and an element in

C

a

cover

. A

cover contact graph (CCG)

has a vertex for each element of

C

and an edge between two vertices whenever the corresponding cover elements touch. It is known how to construct, for any given point seed set, a disk or triangle cover whose contact graph is 1- or 2-connected but the problem of deciding whether a

k

-connected

CCG

can be constructed or not for

k

> 2 is still unsolved. A

triangle cover contact graph (TCCG)

is a cover contact graph whose cover elements are triangles. In this paper, we give an algorithm to construct a 4-connected

TCCG

for a given set of point seeds. We also show that any outerplanar graph has a realization as a

TCCG

on a given set of collinear point seeds. Note that, under this restriction, only trees and cycles are known to be realizable as

CCG

.

Md. Iqbal Hossain, Shaheena Sultana, Nazmun Nessa Moon, Tahsina Hashem, Md. Saidur Rahman

Logspace and FPT Algorithms for Graph Isomorphism for Subclasses of Bounded Tree-Width Graphs

We give a deterministic logspace algorithm for the graph isomorphism problem for graphs with bounded tree-depth. We also show that the graph isomorphism problem is fixed parameter tractable for a related parameterized graph class where the graph parameter is the length of the longest cycle.

Bireswar Das, Murali Krishna Enduri, I. Vinod Reddy

Erratum: Competitive Analysis for Multi-Objective Online Algorithms

We identify an error in the analysis of the online algorithm $\textsc{rpp-mult}$ for the bi-objective time series search problem presented in [1]. The strong competitive ratio with respect to $f_2(c) = \frac{1}{k} \sum_{i=1}^k c_i$ of $\textsc{rpp-mult}$ stated in [1, Theorem 3] does not hold due to an error in the proof. In the following, we point out this error. For details about the problem and the terminology, we refer to the original paper.In the course of the proof of [1, Theorem 3], the expression$$\max_{x \in \mathcal{I}_1} \left\{\frac{M_1}{x} + \frac{M_2x}{z^{\star}} \right\}$$is considered (see Equation (9)). Here, the maximum is falsely determined as $x^*= \sqrt{{(M_1z^{\star})}{M_2}}$. In fact, $x^* \notin \mathcal{I}_1$, and, thus, Equation (9) does not hold. The same mistake has been made in Equation (11), i.e., the chosen maximum is not a point in $\mathcal{I}_2$.Note that the proof cannot be modified such that the stated competitive ratio is proven. However, in [2], a best possible algorithm for the bi-objective time series search problem is presented, as outlined below.Hasegawa and Itoh define the online algorithm Balanced Price Policybpp k for the k-objective time series search problem with respect to an arbitrary monotone continuous function f: ℝk → ℝ, see Algorithm 1.Let $z_k^f = \sup_{\left(x_1,\dots,x_k\right) \in \mathcal{S}_f^k} f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right)$, where$\mathcal{S}_f^k = \left\{ (x_1,\dots,x_k) \in I_1 \times \cdots \times I_k: f\left(\frac{M_1}{x_1},\dots,\frac{M_k}{x_k}\right) = f\left(\frac{x_1}{m_1},\dots,\frac{x_k}{m_k}\right)\right\}$with I i  = [m i ,M i ] for i = 1,…,k.Hasegawa and Itoh prove that, for any integer k ≥ 1 and any monotone continuous function f: ℝk → ℝ, the competitive ratio of $\textsc{bpp}_k$ with respect to f is given by $z_f^k$ and this is the best possible competitive ratio, see [2, Section 4.1].By means of this result, the following theorem gives the best possible competitive ratio with respect to f2 and k = 2:Theorem 1 (Hasegawa and Itoh, [2, Theorem 6.1]).With respect to the function f2 for k = 2, the following holds:$z^2_{f_2} = \frac{1}{2}\left\lbrack \sqrt{\left(\frac{1}{2}\left(\frac{M_2}{m_2}-1\right)\right)^2 + \frac{M_1}{m_1}} + \frac{1}{2}\left(\frac{M_2}{m_2}+1\right) \right \rbrack.$References1Tiedemann, M. and Ide, J. and Schöbel, A.: Competitive Analysis for Multi-Objective Online Algorithms. In: Proceedings of the 9th Workshop on Algorithms and Computation (WALCOM). LNCS, vol. 8973, pp. 210–221 (2015)2Hasegawa, S. and Itoh, T.: Optimal Online Algorithms for the Multi-Objective Time Series Search Problem. arXiv:1506.04474v4 [cs.DS] (2015)

Morten Tiedemann, Jonas Ide, Anita Schöbel

Backmatter

Weitere Informationen

Premium Partner

Bildnachweise