ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Largest Chordal and Interval Subgraphs Faster than $$2^n$$ 2 n (2015)

Springer

In: Algorithmica

add to mindlist on the mindlist

Details

Publication Date: 2015-08-22

Description: 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 $\mathcal {O}(2^{\lambda n})$ for some $\lambda 〈1$ . These are the first algorithms breaking the trivial $2^n n^{\mathcal {O}(1)}$ bound of the brute-force search for these problems.

Print ISSN: 0178-4617

Electronic ISSN: 1432-0541

Topics: Computer Science , Mathematics

Published by Springer

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit