Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorVillanger, Yngve
dc.date.accessioned2016-05-30T11:03:27Z
dc.date.available2016-05-30T11:03:27Z
dc.date.issued2010
dc.PublishedLeibniz International Proceedings in Informatics 2010, 5:383-394eng
dc.identifier.urihttps://hdl.handle.net/1956/12037
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.language.isoengeng
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BY-ND 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/eng
dc.subjectBounded treewidtheng
dc.subjectminimal triangulationeng
dc.subjectmoderately exponential timeeng
dc.titleFinding Induced Subgraphs via Minimal Triangulationsen_US
dc.typeConference object
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2016-04-07T06:45:37Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright F. V. Fomin and Y. Villangeren_US
dc.identifier.doihttps://doi.org/10.4230/lipics.stacs.2010.2470
dc.identifier.cristin516177
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US


Files in this item

Thumbnail

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