Standard

Largest chordal and interval subgraphs faster than 2n. / Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve.

Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings. 2013. p. 193-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8125 LNCS).

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

Harvard

Bliznets, I, Fomin, FV, Pilipczuk, M & Villanger, Y 2013, Largest chordal and interval subgraphs faster than 2n. in Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8125 LNCS, pp. 193-204, 21st Annual European Symposium on Algorithms, ESA 2013, Sophia Antipolis, France, 2/09/13. https://doi.org/10.1007/978-3-642-40450-4_17

APA

Bliznets, I., Fomin, F. V., Pilipczuk, M., & Villanger, Y. (2013). Largest chordal and interval subgraphs faster than 2n. In Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings (pp. 193-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8125 LNCS). https://doi.org/10.1007/978-3-642-40450-4_17

Vancouver

Bliznets I, Fomin FV, Pilipczuk M, Villanger Y. Largest chordal and interval subgraphs faster than 2n. In Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings. 2013. p. 193-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-40450-4_17

Author

Bliznets, Ivan ; Fomin, Fedor V. ; Pilipczuk, Michał ; Villanger, Yngve. / Largest chordal and interval subgraphs faster than 2n. Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings. 2013. pp. 193-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{67fe1184e7234734abf21709969e12c4,
title = "Largest chordal and interval subgraphs faster than 2n",
abstract = "We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2 λn) for some λ < 1. These are the first algorithms breaking the trivial 2n nO(1) bound of the brute-force search for these problems.",
author = "Ivan Bliznets and Fomin, {Fedor V.} and Micha{\l} Pilipczuk and Yngve Villanger",
year = "2013",
month = sep,
day = "24",
doi = "10.1007/978-3-642-40450-4_17",
language = "English",
isbn = "9783642404498",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "193--204",
booktitle = "Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings",
note = "21st Annual European Symposium on Algorithms, ESA 2013 ; Conference date: 02-09-2013 Through 04-09-2013",

}

RIS

TY - GEN

T1 - Largest chordal and interval subgraphs faster than 2n

AU - Bliznets, Ivan

AU - Fomin, Fedor V.

AU - Pilipczuk, Michał

AU - Villanger, Yngve

PY - 2013/9/24

Y1 - 2013/9/24

N2 - We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2 λn) for some λ < 1. These are the first algorithms breaking the trivial 2n nO(1) bound of the brute-force search for these problems.

AB - We prove that in an n-vertex graph, induced chordal and interval subgraphs with the maximum number of vertices can be found in time O(2 λn) for some λ < 1. These are the first algorithms breaking the trivial 2n nO(1) bound of the brute-force search for these problems.

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

U2 - 10.1007/978-3-642-40450-4_17

DO - 10.1007/978-3-642-40450-4_17

M3 - Conference contribution

AN - SCOPUS:84884324389

SN - 9783642404498

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

SP - 193

EP - 204

BT - Algorithms, ESA 2013 - 21st Annual European Symposium, Proceedings

T2 - 21st Annual European Symposium on Algorithms, ESA 2013

Y2 - 2 September 2013 through 4 September 2013

ER -

ID: 49788021