Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorVillanger, Yngve
dc.description.abstractPotential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in- cluding Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques, and an integer t, it is possible in time the number of potential maximal cliques times O(nO(t)) to find a maximum induced subgraph of treewidth t in G and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time O(1.734601n ), this yields that both the problems are solvable in time 1.734601n * nO(t) .en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-ND 3.0eng
dc.subjectBounded treewidtheng
dc.subjectminimal triangulationeng
dc.subjectmoderately exponential timeeng
dc.titleFinding Induced Subgraphs via Minimal Triangulationsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright F. V. Fomin and Y. Villangeren_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US
dc.identifier.citationLeibniz International Proceedings in Informatics 2010, 5:383-394

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY-ND 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY-ND 3.0