Standard

Largest Chordal and Interval Subgraphs Faster than 2 n. / Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve.

In: Algorithmica, Vol. 76, No. 2, 01.10.2016, p. 569-594.

Research output: Contribution to journal › Article › peer-review

Harvard

Bliznets, I, Fomin, FV, Pilipczuk, M & Villanger, Y 2016, 'Largest Chordal and Interval Subgraphs Faster than 2 n', Algorithmica, vol. 76, no. 2, pp. 569-594. https://doi.org/10.1007/s00453-015-0054-2

APA

Bliznets, I., Fomin, F. V., Pilipczuk, M., & Villanger, Y. (2016). Largest Chordal and Interval Subgraphs Faster than 2 n. Algorithmica, 76(2), 569-594. https://doi.org/10.1007/s00453-015-0054-2

Vancouver

Bliznets I, Fomin FV, Pilipczuk M, Villanger Y. Largest Chordal and Interval Subgraphs Faster than 2 n. Algorithmica. 2016 Oct 1;76(2):569-594. https://doi.org/10.1007/s00453-015-0054-2

Author

Bliznets, Ivan ; Fomin, Fedor V. ; Pilipczuk, Michał ; Villanger, Yngve. / Largest Chordal and Interval Subgraphs Faster than 2 n. In: Algorithmica. 2016 ; Vol. 76, No. 2. pp. 569-594.

BibTeX

@article{a53b38e0ffb14f4ea8a265c634236a02,
title = "Largest Chordal and Interval Subgraphs Faster than 2 n",
abstract = "We prove that in a graph with n vertices, 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 2 nnO(1) bound of the brute-force search for these problems.",
keywords = "Chordal graphs, Exact exponential algorithms, Interval graphs, Maximum induced Π-subgraph",
author = "Ivan Bliznets and Fomin, {Fedor V.} and Micha{\l} Pilipczuk and Yngve Villanger",
year = "2016",
month = oct,
day = "1",
doi = "10.1007/s00453-015-0054-2",
language = "English",
volume = "76",
pages = "569--594",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer Nature",
number = "2",

}

RIS

TY - JOUR

T1 - Largest Chordal and Interval Subgraphs Faster than 2 n

AU - Bliznets, Ivan

AU - Fomin, Fedor V.

AU - Pilipczuk, Michał

AU - Villanger, Yngve

PY - 2016/10/1

Y1 - 2016/10/1

N2 - We prove that in a graph with n vertices, 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 2 nnO(1) bound of the brute-force search for these problems.

AB - We prove that in a graph with n vertices, 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 2 nnO(1) bound of the brute-force search for these problems.

KW - Chordal graphs

KW - Exact exponential algorithms

KW - Interval graphs

KW - Maximum induced Π-subgraph

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

U2 - 10.1007/s00453-015-0054-2

DO - 10.1007/s00453-015-0054-2

M3 - Article

AN - SCOPUS:84939864841

VL - 76

SP - 569

EP - 594

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 2

ER -

ID: 49787594