𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The algorithmic complexity of colour switching

✍ Scribed by Yeow Meng Chee; Andrew Lim

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
477 KB
Volume
43
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Algorithmic complexity of protein identi
Algorithmic complexity of protein identification: combinatorics of weighted strings
✍ Mark Cieliebak; Thomas Erlebach; Zsuzsanna LiptΓ‘k; Jens Stoye; Emo Welzl πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 319 KB

We investigate a problem which arises in computational biology: Given a constant-size alphabet A with a weight function : A β†’ N, ΓΏnd an e cient data structure and query algorithm solving the following problem: For a string over A and a weight M ∈ N, decide whether contains a substring with weight M

Greedy algorithms, H-colourings and a co
Greedy algorithms, H-colourings and a complexity-theoretic dichotomy
✍ Antonio Puricella; Iain A. Stewart πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 566 KB

Let H be a ΓΏxed undirected graph. An H -colouring of an undirected graph G is a homomorphism from G to H . If the vertices of G are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically ΓΏrst maximal Hcolourable subgraphs of G. We show that

The complexity of G-free colourability
The complexity of G-free colourability
✍ Demetrios Achlioptas πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 758 KB

The problem of determining if a graph is 2-colourable (i.e., bipartite) has long been known to have a simple polynomial time algorithm. Being 2-colourable is equivalent to having a bipartition of the vertex set where each cell is &-free. We extend this notion to determining if there exists a biparti