Alan Gibbons

TCS Journal 2004 Journal Article

Rotation sequences and edge-colouring of binary tree pairs

• Alan Gibbons
• Paul Sant

The famous four-colour problem of planar maps is equivalent, by an optimally fast reduction, to the problem of colouring pairs of binary trees (CPBT). Extant proofs of the four colour theorem lack conciseness, are not lucid in their detail and require hours of electronic computation. The search for a more satisfactory proof continues and, in this spirit, we explore one approach to CPBT based upon the rotation operation in binary trees. We prove that a more satisfactory proof exists if a rotational path between the two trees of every problem instance satisfies our non-colour-clashing sequence conjecture.

MFCS Conference 2002 Invited Paper

Edge-Colouring Pairs of Binary Trees: Towards a Concise Proof of the Four-Colour Theorem of Planar Maps

• Alan Gibbons
• Paul Sant

Abstract The famous Four-colour Problem (FCP) of planar maps is equivalent, by an optimally fast reduction, to the problem of Colouring Pairs of Binary Trees (CPBT). Extant proofs of FCP lack conciseness, lucidity and require hours of electronic computation. The search for a satisfactory proof continues and, in this spirit, we explore two approaches to CPBT. In the first, we prove that a satisfactory proof exists if the rotational path between the two trees of the problem instance always satisfies a specific condition embodied in our Shortest Path Conjecture. In our second approach, we look for patterns of colourability within regular forms of tree pairs and seek to understand all instances of CPBT as a perturbation of these. In this Colouring Topologies approach, we prove, for instance, that concise proofs to CPBT exist for instances contained within many infinite-sized sets of trees.

TCS Journal 2001 Journal Article

Efficient web searching using temporal factors

• Artur Czumaj
• Ian Finch
• Leszek Ga̧sieniec
• Alan Gibbons
• PAUL LENG
• Wojciech Rytter
• Michele Zito

We study the issues involved in the design of algorithms for performing information gathering more efficiently, by taking advantage of anticipated variations in access times in different regions at different times of the day or week. We look at the problem theoretically, as a generalisation of single processor sequencing with release times and deadlines, in which performance times (lengths) of the tasks can change in time. The new problem is called Variable Length Sequencing Problem (VLSP). We show that although the decision version of VLSP seems to be intractable in the general case, it can be solved optimally for lengths 1 and 2. This result opens the possibility of practicable algorithms to schedule searches efficiently when expected access times can be categorised as either slow or fast. Some algorithms for more general cases are examined and complexity results derived.

TCS Journal 2000 Journal Article

Complexity-theoretic models of phase transitions in search problems

• Paul E. Dunne
• Alan Gibbons
• Michele Zito

In recent years, numerous studies have observed that many hard combinatorial decision problems exhibit behaviour described as a ‘phase-transition’. This is the phenomenon whereby typical instances of a problem display a dramatic shift in certain characteristics as some parameter of the instances is varied. Such characteristics include the likelihood of an instance having a solution and the time taken by a search algorithm. The apparent pervasiveness of phase-transitions in hard combinatorial search problems has led to contrasting claims being advanced concerning to what extent all NP-complete problems exhibit phase-transitions. The established importance of exploiting phase-transition effects in the design of search heuristics provides a strong motivation for assessing how valid such claims may be. In this paper we argue that questions concerning the generality of phase-transition phenomena are, at present, ill-defined. In order to address this difficulty, we propose and examine rigorous complexity-theoretic models of the statement ‘the decision problem D has a phase-transition’. Within these models it is proved that for certain ‘natural’ definitions contrasting results about phase-transition behaviour can be proved.

SODA Conference 2000 Conference Paper

Deterministic broadcasting in unknown radio networks

• Bogdan S. Chlebus
• Leszek Gasieniec
• Alan Gibbons
• Andrzej Pelc
• Wojciech Rytter

MFCS Conference 1999 Conference Paper

Efficiency of Fast Parallel Pattern Searching in Highly Compressed Texts

• Leszek Gasieniec
• Alan Gibbons
• Wojciech Rytter

Abstract We consider efficiency of NC -algorithms for pattern-searching in highly compressed one- and two-dimensional texts. “Highly compressed” means that the text can be exponentially large with respect to its compressed version, and “fast” means “in polylogarithmic time”. Given an uncompressed pattern P and a compressed version of a text T, the compressed matching problem is to test if P occurs in T. Two types of closely related compressed representations of 1-dimensional texts are considered: the Lempel-Ziv encodings (LZ, in short) and restricted LZ encodings (RLZ, in short). For highly compressed texts there is a small difference between them, in extreme situations both of them compress text exponentially, e. g. Fibonacci words of size N have compressed versions of size O (log N ) for LZ and Restricted LZ encodings. Despite similarities we prove that LZ -compressed matching is P-complete while RLZ -compressed matching is rather trivially in NC. We show how to improve a naive straightforward NC algorithm and obtain almost optimal parallel RLZ-compressed matching applying tree-contraction techniques to directed acyclic graphs with polynomial tree-size. As a corollary we obtain an almost optimal parallel algorithm for LZW-compressed matching which is simpler than the (more general) algorithm in [ 11 ]. Highly compressed 2-dimensional texts are also considered.

TCS Journal 1997 Journal Article

Parallel algorithms for the minimum cut and the minimum length tree layout problems

• Josep Díaz
• Alan Gibbons
• Grammati E. Pantziou
• Maria J. Serna
• Paul G. Spirakis
• Jacobo Toran

The minimum cut and minimum length linear arrangement problems usually occur in solving wiring problems and have a lot in common with job sequencing questions. Both problems are NP-complete for general graphs and in P for trees. We present here two parallel algorithms for the CREW PRAM. The first solves the minimum length linear arrangement problem for trees and the second solves the minimum cut arrangement for trees. We prove that the first problem belongs to NC for trees, and the second problem is in NC for bounded degree trees. To the best of our knowledge, these are the first parallel algorithms for the minimum length and the minimum cut linear arrangement problems.

TCS Journal 1996 Journal Article

Guthrie's problem: new equivalences and rapid reductions

• Artur Czumaj
• Alan Gibbons

In 1977, Appel and Haken proved that every planar graph is four vertex colourable which finally proved Guthrie's conjecture of circa 1852 that four colours are always sufficient. Their proof is very long and the implicit algorithm for four colouring is rather impractical. This paper provides a new characterisation of the four-colour problem by showing that it is equivalent (by an optimally fast reduction) to a simply stated problem of 3-edge colouring pairs of trees. This new problem, in turn, is equivalent to nontrivial subclasses of other problems in mathematics and computer science of which we describe three. These are problems of intersection of regular languages, of integer linear equations and of algebraic expressions. In the general case, all these problems require exponential time to solve. We show that if these problems are defined on pairs of trees, then polynomial time is sufficient. In addition, these problems offer enticing opportunities in the search for a shorter proof of the four-colour theorem and for more practical algorithms for four-colouring planar graphs.

MFCS Conference 1996 Invited Paper

Models of DNA Computation

• Alan Gibbons
• Martyn Amos
• David A. Hodgson

Abstract The idea that living cells and molecular complexes can be viewed as potential machinic components dates back to the late 1950s, when Richard Feynman delivered his famous paper describing sub-microscopic computers. Recently, several papers have advocated the realisation of massively parallel computation using the techniques and chemistry of molecular biology. Algorithms are not executed on a traditional, siliconbased computer, but instead employ the test-tube technology of genetic engineering. By representing information as sequences of bases in DNA molecules, existing DNA-manipulation techniques may be used to quickly detect and amplify desirable solutions to a given problem. We review the recent spate of papers in this field and take a critical view of their implications for laboratory experimentation. We note that extant models of DNA computation are flawed in that they rely upon certain error-prone biological operations. The one laboratory experiment that is seminal for current interest and claims to provide an efficient solution for the Hamiltonian path problem has proved to be unrepeatable by other researchers. We introduce a new model of DNA computation whose implementation is likely to be far more error-resistant than extant proposals. We describe an abstraction of the model which lends itself to natural algorithmic description, particularly for problems in the complexity class NP. In addition we describe a number of linear-time parallel algorithms within our model, particularly for NP -complete problems. We describe an “in vitro” realisation of the model and conclude with a discussion of future work and outstanding problems.

SODA Conference 1996 Conference Paper

RNC Algorithms for the Uniform Generation of Combinatorial Structures

• Michele Zito 0001
• Ida Pu
• Martyn Amos
• Alan Gibbons

TCS Journal 1990 Journal Article

Optimally edge-colouring outerplanar graphs is in NC

• Alan Gibbons
• Wojciech Rytter

We prove that every outerplanar graph can be optimally edge-coloured in polylogarithmic time using a polynomial number of processors on a parallel random access machine without write conflicts (P-RAM).

I&C Journal 1989 Journal Article

Optimal parallel algorithms for dynamic expression evaluation and context-free recognition

• Alan Gibbons
• Wojciech Rytter

We describe a deterministic parallel algorithm to evaluate algebraic expressions in O(log n) time using n log(n) processors on a parallel random access machine without write conflicts (P-RAM) and with no free preprocessing. The input to the algorithm is a string (of the symbols making up the expression) store in an array. Such a form for the input enables a consecutive numbering of the operands in the expression in O(log(n)) time with n log(n) processors. This corresponds to a consecutive numbering of the leaves of the expression tree. This then further permits us to partition the leaves into small segments. We improve the result of Miller and Reif (1985, in “26th IEEE Sympos. on Found. of Comput. Sci. ,” pp. 478–489), who described an optimal parallel randomized algorithm. (Strictly speaking, the input to their algorithm is different being the parse tree of the expression. The input to the innovative part of our algorithm (step 2) is this parse tree which, in addition, has its leaves numbered consecutively from left to right. These two orms are equivalent if we note that such a numbering can be obtained by an optimal parallel algorithm which employs the Euler tour technique and optimal list ranking). Our algorithm can be used to construct optimal parallel algorithms for the recognition of two nontrival subclasses of context-free languages: bracket and input-driven languages. These languages are the most complicated context-free languages known to be recognizable in deterministic logarithmic space. This strengthens the result of Matheyses and Fiduccia (1982 in “20th Allerton Conf. on Commun. Control and Comput. ”) who constructed an almost optimal parallel algorithm for Dyck languages, since Dyck languages are a proper subclass of input-driven languages. Our algorithm includes a new simple method for tree contraction which we call the leaves-cutting method. Its correctness is trival (compared with the method of Miller and Reif) and it can be implemented on a P-RAM without write and without read conflicts.

TCS Journal 1986 Journal Article

On the decidability of some problems about rational subsets of free partially commutative monoids

• Alan Gibbons
• Wojciech Rytter

Let I = A ∪ B be a partially commutative alphabet such that two letters commute iff one of them belongs to A and the other one belongs to B. Let M = A∗ × B∗ denote the free partially commutative monoid generated by I. We consider the following six problems for rational (given by regular expressions) subsets, X, Y of M: (Q1): X∪Y=0? (Q2): X⊆Y? (Q3): X=Y? (Q4): X=M? (Q5): M−X finite? (Q6): X is recognized? It is known (see (Berstel, 1979)) that all these problems are undecidable if Card A > 1 and Card B > 1, and they are decidable if Card A = Card B = 1 (Card U denotes the cardinality of U). It was conjectured (see (Choffrut, 1986, p. 79)) that these problems are decidable in the remaining cases, where Card A = 1 and Card B > 1. In this paper we show that if Card A = 1 and Card B > 1, then the problem (Q1) is decidable, and problems (Q2)–(Q6) are undecidable. Our paper is an application of results concerning reversal-bounded, nondeterministic, multicounter machines and nondeterministic, general sequential machines.