Organizers 

Bangladesh Atomic Energy Commission
Bangladesh Academy of Sciences

BUET

Publisher

Journal Special Issues

Sponsors

Supported by

IEICE Technical Committee on Theoretical Foundations of Computing (COMP) 

Special Interest Group for ALgorithms (SIGAL) of the Information Processing Society of Japan (IPSJ)

News

11, Nov 2014
Notification has been sent. List of accepted papers has been published. Acceptance rate ~30% for full papers (~34% including the short papers).

26, Sep 2014
Paper submission is now closed. We have a total of 88 submissions.

16, Sep 2014 
Paper submission deadline is extended. Extended deadline: 25 (Thu.) September, 2014 (23:59:59 GMT/UTC)

16, May 2014 
WALCOM 2015 is supported by Special Interest Group for ALgorithms (SIGAL) of the Information Processing Society of Japan (IPSJ)

17, Mar 2014 
Journal of Graph Algorithms and Applications and Journal of Discrete Algorithms will publish special issues dedicated to WALCOM 2015

08, Mar 2014 
WALCOM 2015 is supported by IEICE Technical Committee on Theoretical Foundations of Computing (COMP)  

08, Mar 2014 
WALCOM 2015 proceedings will be published in LNCS

20, Feb 2014
WALCOM 2015 CFP is published

20, Feb 2014 
WALCOM 2015 Website is up and running


 

WALCOM 2015 Accepted Papers with Abstracts

Ken Iwaide and Hiroshi Nagamochi. An Improved Algorithm for Parameterized Edge Dominating Set Problem
Abstract: An edge dominating set of a graph G = (V, E) is a subset M 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.
Mark de Berg and Ali D. Mehrabi. Straight-Path Queries in Trajectory Data
Abstract: 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 \emph{dilation} and \emph{directedness}, and present efficient construction algorithms for our data structures, and analyze their performance. %We give efficient algorithms to construct our data structures, we analyze their performance from a theoretical point of view, and we compare their performance experimentally.

We also present an $O(n^{1.5+\eps})$ algorithm for the following simplification problem: given a trajectory $\tr$ and a threshold~$\tau$, find a simplification of~$\tr$ with a minimum number of vertices such that each edge in the simplification replaces a sub-trajectory whose length is at most $\tau$ times the length of the edge. This significantly improves the fastest known algorithm for the problem.
Li Guan and Weidong Li. The directed ring loading with penalty cost
Abstract: We study the directed ring loading problem with penalty cost, which is to select some of given multicast requests with different demands and embed them in a directed ring, such that the sum of the maximum congestion of the 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 design a 1.58-approximation algorithm for the demand divisible case and a 3-approximation algorithm for the demand indivisible case. As a consequence, for any $\varepsilon>0$, we present a ($1.58+\varepsilon$)-approximation algorithm for the case where
every multicast request contains exactly one sink.
Md. Iqbal Hossain, Shaheena Sultana, Nazmun Nessa Moon, Tahsina Hashem and Md. Saidur Rahman. On Triangle Cover Contact Graphs [Short Paper]
Abstract: Let $S=\{p_1,p_2,\ldots,p_n\}$ be a set of pairwise disjoint geometric objects of some type and $C=\{c_1,c_2,\ldots,c_n\}$ be a set of closed objects of some type with the property that each element in $C$ covers exactly one element in $S$ and any two elements in $C$ can intersect only on their boundaries. We call an element in $S$ a \textit{seed} and an element in $C$ a \textit{cover}. A \textit{cover contact graph ($CCG$)} consists of a set of vertices and a set of edges where each of the vertex corresponds to each of the covers and each edge corresponds to a connection between two covers if they touch at their boundaries. The problem of deciding whether a resulting $CCG$ is 1- or 2-connected has already been solved but the problem of deciding whether a resulting $CCG$ is $k$-connected for $k > 2$ is still unsolved where each cover element is a disk or a triangle. A \textit{triangle cover contact graph ($TCCG$)} is a cover contact graph whose cover elements are triangles. In this paper, we give algorithms to construct a 3-connected $TCCG$ and 4-connected $TCCG$ for a given set of seeds. Furthermore we also present an algorithm to show that a given outerplanar graph has a realization as a $TCCG$ on a given set of collinear seeds. Note that only trees and cycles are known to be realizable as $CCG$.
Christian Engels. Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Abstract: 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.
Thim Strothmann. The impact of communication patterns on distributed locally self-adjusting binary search trees
Abstract: This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm, which 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.
Johannes Fischer and Daniel Peters. A Practical Succinct Data Structure for Tree-Like Graphs
Abstract: 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 roughly 20, while increasing the worst-case running times for the operations by roughly the same factor.
Michael A. Bekos, Thomas C. Van Dijk, Philipp Kindermann and Alexander Wolff. Simultaneous Drawing of Planar Graphs with Right-Angle Crossings and Few Bends
Abstract: Given two planar graphs that are defined on the same set of vertices, a RAC simultaneous drawing is one in which each graph is drawn planar, there are no edge overlaps and the crossings between the two graphs form right angles. The geometric version restricts the problem to straight-line drawings. It is known, however, that there exists a wheel and a matching which do not admit a geometric RAC simultaneous drawing.

In order to enlarge the class of graphs that admit RAC simultaneous drawings, we allow bends in the resulting drawings. We prove that two planar graphs always admit a RAC simultaneous drawing with six bends per edge each, in quadratic area. For more restricted classes of planar graphs (i.e., matchings, paths, cycles, outerplanar graphs and subhamiltonian graphs), we manage to significantly reduce the required number of bends per edge, while keeping the area quadratic.
Yuji Obata and Takao Nishizeki. Edge-Colorings of Weighted Graphs
Abstract: Let G be a graph with a positive integer weight ω(v) for each vertex v. One wishes to assign each edge e 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 three efficient algorithms to nd an ω-edge-coloring of a given graph. One of them nds an ω-edge-coloring with span smaller than twice the ω-chromatic index. We also obtain several upper bounds and lower bounds on
the !-chromatic index.
Wei-Yin Lin, Yen-Wei Wu, Hung-Lung Wang and Kun-Mao Chao. Forming Plurality at Minimum Cost
Abstract: 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.
Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara and Yushi Uno. Folding a Paper Strip to Minimize Thickness
Abstract: 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 both problems fixed-parameter tractable in 1D with respect to the number of layers.
Franz Brandenburg, Niklas Heinsohn, Michael Kaufmann and Daniel Neuwirth. On Bar (1, j)-Visibility Graphs
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 edgesegment 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 edgesegments. 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, infinity)-visible.
Yuma Asada and Michiko Inoue. An Efficient Silent Self-Stabilizing Algorithm for 1-Maximal Matching in Anonymous Networks
Abstract: 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.
Yoshiaki Araki, Takashi Horiyama and Ryuhei Uehara. Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid
Abstract: 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.
Jérémy Barbay, Ankur Gupta, Srinivasa Rao Satti and Jonathan Sorenson. Dynamic Online Multiselection in Internal and External Memory
Abstract: We consider the dynamic version of the \emph{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 Kaligosi\etal [ICALP 2005].
In particular, we extend the results of Barbary\etal [ESA 2013] by supporting arbitrary \emph{insertions} and \emph{deletions} while supporting online \emph{select} and \emph{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.
Bireswar Das, Murali Krishna Enduri and I. Vinod Reddy. Logspace and FPT Algorithms for Graph Isomorphism for Subclasses of Bounded Tree-width Graphs [Short Paper]
Abstract: The graph isomorphism problem (GI) is to decide whether two graphs are isomorphic.
This problem has considerable importance in complexity theory due to its unresolved complexity status. 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 parameterized graph class where the graph parameter is the length of the longest cycle.
Kei Uchizawa, Daiki Yashima and Xiao Zhou. Threshold Circuits for Global Patterns in 2-Dimensional Maps
Abstract: In this paper, we consider a biologically-inspired Boolean function, called PnD,  which models a task for detecting specific global spatial arrangements of  local visual patterns on a 2-dimensional map. We prove that PnD 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 PnD  needs size $\Omega(\sqrt{n}/\log n)$.
Ehsan Emamjomeh-Zadeh, Mohammad Ghodsi, Hamid Homapour and Masoud Seddighin. Bounds on Color-Spanning Set Unit Covering
Abstract: In this paper, we consider a new problem of finding bounds on unit covering in color-spanning set model:
Given a set of $n$ points in $d$-dimensional plane colored with $m$ colors, \emph{MinCSBC} problem is to select $m$ points of different colors minimizing the minimum number of unit balls needed to cover them. Similarly, \emph{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 either even in one dimension. For $d=1$ we propose an $\ln(m)$-approximation algorithm and also, we present a constant-factor approximation algorithm for fixed $f$ where $f$ is the maximum frequency of the colors. For MaxCSBC problem, we first prove the NP-hardness. Then, we present an approximation algorithm within a factor $1/2$ in one-dimensional case.
Subhash Bhagat, Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Fault-tolerant Gathering of Asynchronous, Oblivious Mobile Robots Under One-axis Agreement
Abstract: In this paper, we have studied one of the fundamental coordination problem for multi robot system, namely {\it gathering}, for $n \ge 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.
Takahisa Toda, Shogo Takeuchi, Koji Tsuda and Shin-Ichi Minato. Superset Generation on Decision Diagrams [Short Paper]
Abstract: 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.
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.
Furthermore, we apply our superset generation method to hitting set generation.
Diptarka Chakraborty and Raghunath Tewari. Simultaneous Time-Space Upper Bounds for Red-Blue Path Problem in Planar DAGs
Abstract: In this paper, we consider the {\RB} 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 {\RB} problem in planar DAGs is {\NL}-complete. We exhibit a polynomial time and $O(\sspace)$ space algorithm (for any $\epsilon >0$) for the {\RB} problem in planar DAG.
We also consider a natural relaxation of {\RB} problem, denoted as {\EB} problem. The {\EB} problem in DAGs is known to be {\NL}-complete. We provide a polynomial time and $O(\sspace)$ space (for any $\epsilon >0$) bound for {\EB} problem in planar DAGs.
Sang Won Bae. An Almost Optimal Algorithm for Voronoi Diagrams of Non-Disjoint Line Segments
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 \alpha(n) \log n + k)$ time, where $\alpha(\cdot)$ 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 $\Omega(n \log n + k)$ in the worst case, our algorithm is worst-case optimal for $k = \Omega(n \alpha(n) \log n)$, and is only a factor of $\alpha(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.
Gaurav Singh, N.S. Narayanaswamy and Ramakrishna G.. Approximate Distance Oracle in $O(n^2)$ Time and $O(n)$ Space for Chordal Graphs
Abstract: 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\in V(G), 1 \leq i,j \leq n$, we take constant time to output a distance value $d_{ij} \leq 2d_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.376})$ 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.
Seungbum Jo, Rajeev Raman and Srinivasa Rao Satti. Compact encodings and indexes for the nearest larger neighbor problem
Abstract: Given a d-dimensional array, for any integer d > 0, the nearest larger neighbor (NLN) 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 a data structure version of this problem, where we need to preprocess a given sequence of elements to construct a data structure that can answer NLN queries efficiently.
We also consider the version when only the nearest larger right neighbor (NLRN) is sought, in one dimension. For this problem, for an array of length n, we obtain an index that takes O((n/c) log c) bits, and supports NLRN queries in O(c) time, for any any parameter c, where $1 \le c \le n$, improving the earlier result of Jayapaul et al. [IWOCA, 2014].
In the two-dimensional case, for an $n \times n$ array $A$, we give a $O(n^2)$-bit (optimal) encoding that supports NLN queries (although, not efficiently). When $A$ is a binary matrix, we describe an $O(n^2)$-bit encoding that supports NLN queries in O(1) time, and also an index of size O(n^2/c) bits that supports NLN queries in O(c) time, for any parameter c, where $1 \le c \le n$.
Morten Tiedemann, Jonas Ide and Anita Schöbel. Competitive Analysis for Multi-Objective Online Algorithms
Abstract: 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.
Venkatesan Chakaravarthy, Neelima Gupta, Aditya Pancholi and Sambuddha Roy. Fast algorithms for constrained graph density problems
Abstract: 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 'lp's. 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 a general class of constraints called co-matroid constraints. We also consider the minimum degree objective: we obtain efficient algorithms for this objective subject to both co-matroid and dependency constraints. Our algorithms heavily utilize the core decomposition of a graph.
Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi and Shin-Ichi Minato. Enumerating Eulerian Trails via Hamiltonian Path Enumeration
Abstract: Given an undirected graph G, we consider enumerating all Eulerian trails, that is, trails containing all edges in G. 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 set of paths. First we compute the line graph L(G), the graph representing adjacency of the edges in G. Because every Eulerian trail in G corresponds to a Hamiltonian path in L(G) but the converse is not true, we also formulated the condition when a Hamiltonian path in L(G) corresponds to an Eulerian trail in G. Then we enumerate all Hamiltonian paths in L(G) satisfying the condition with the help of ZDD.
Santiago Ravelo and Carlos Ferreira. PTAS's for Some Metric p-Source Communication Spanning Tree Problems
Abstract: 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 w(e) associated to each edge satisfying the triangular inequality, a subset S of V with p vertices and non-negative routing requirements r(u,v) between all pairs of nodes u in S and v in V, the metric p-OCT's objective is to find a spanning tree T of G, that minimizes the sum of routing costs over T of all pairs of vertices, where the routing cost over T between vertices u in S and v in V is r(u,v)d(T, u,v) being d(H,x,y) the minimum distance between nodes x and y in a subgraph H of 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.
Michael Soltys and Neerja Mhaskar. Non-repetitive strings over alphabet lists
Abstract: A word is non-repetitive if it does not contain a subword of the form vv. Given a list of alphabets L = L1, L2, . . . , Ln, we investigate the question of generating non-repetitive words w = w1w2 . . . wn, such that the symbol wi is a letter in the alphabet Li. 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.
WALCOM '15 Organizing Committee