Standard

Longest common subsequences in permutations and maximum cliques in circle graphs. / Tiskin, Alexander.

Combinatorial Pattern Matching (CPM 2006). 2006. p. 270-281 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Tiskin, A 2006, Longest common subsequences in permutations and maximum cliques in circle graphs. in Combinatorial Pattern Matching (CPM 2006). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4009, pp. 270-281. https://doi.org/10.1007/11780441_25

APA

Tiskin, A. (2006). Longest common subsequences in permutations and maximum cliques in circle graphs. In Combinatorial Pattern Matching (CPM 2006) (pp. 270-281). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4009). https://doi.org/10.1007/11780441_25

Vancouver

Tiskin A. Longest common subsequences in permutations and maximum cliques in circle graphs. In Combinatorial Pattern Matching (CPM 2006). 2006. p. 270-281. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11780441_25

Author

Tiskin, Alexander. / Longest common subsequences in permutations and maximum cliques in circle graphs. Combinatorial Pattern Matching (CPM 2006). 2006. pp. 270-281 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{61ae50116615453f9c9053047b75bb34,
title = "Longest common subsequences in permutations and maximum cliques in circle graphs",
abstract = "For two strings a, b, the longest common subsequence (LCS) problem consists in comparing a and 6 by computing the length of their LCS. In a previous paper, we defined a generalisation, called {"}the all semi-local LCS problem{"}, for which we proposed an efficient output representation and an efficient algorithm. In this paper, we consider a restriction of this problem to strings that are permutations of a given set. The resulting problem is equivalent to the all local longest increasing subsequences (LIS) problem. We propose an algorithm for this problem, running in time O(n1.5) on an input of size n. As an interesting application of our method, we propose a new algorithm for finding a maximum clique in a circle graph on n nodes, running in the same asymptotic time O(n1.5). Compared to a number of previous algorithms for this problem, our approach presents a substantial improvement in worst-case running time. {\textcopyright} Springer-Verlag Berlin Heidelberg 2006.",
author = "Alexander Tiskin",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11780441_25",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "270--281",
booktitle = "Combinatorial Pattern Matching (CPM 2006)",

}

RIS

TY - GEN

T1 - Longest common subsequences in permutations and maximum cliques in circle graphs

AU - Tiskin, Alexander

PY - 2006/1/1

Y1 - 2006/1/1

N2 - For two strings a, b, the longest common subsequence (LCS) problem consists in comparing a and 6 by computing the length of their LCS. In a previous paper, we defined a generalisation, called "the all semi-local LCS problem", for which we proposed an efficient output representation and an efficient algorithm. In this paper, we consider a restriction of this problem to strings that are permutations of a given set. The resulting problem is equivalent to the all local longest increasing subsequences (LIS) problem. We propose an algorithm for this problem, running in time O(n1.5) on an input of size n. As an interesting application of our method, we propose a new algorithm for finding a maximum clique in a circle graph on n nodes, running in the same asymptotic time O(n1.5). Compared to a number of previous algorithms for this problem, our approach presents a substantial improvement in worst-case running time. © Springer-Verlag Berlin Heidelberg 2006.

AB - For two strings a, b, the longest common subsequence (LCS) problem consists in comparing a and 6 by computing the length of their LCS. In a previous paper, we defined a generalisation, called "the all semi-local LCS problem", for which we proposed an efficient output representation and an efficient algorithm. In this paper, we consider a restriction of this problem to strings that are permutations of a given set. The resulting problem is equivalent to the all local longest increasing subsequences (LIS) problem. We propose an algorithm for this problem, running in time O(n1.5) on an input of size n. As an interesting application of our method, we propose a new algorithm for finding a maximum clique in a circle graph on n nodes, running in the same asymptotic time O(n1.5). Compared to a number of previous algorithms for this problem, our approach presents a substantial improvement in worst-case running time. © Springer-Verlag Berlin Heidelberg 2006.

UR - http://www.scopus.com/inward/record.url?scp=33746056885&partnerID=8YFLogxK

U2 - 10.1007/11780441_25

DO - 10.1007/11780441_25

M3 - Conference contribution

AN - SCOPUS:33746056885

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 270

EP - 281

BT - Combinatorial Pattern Matching (CPM 2006)

ER -

ID: 127757635