toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author Liedloff, M.; Montealegre, P.; Todinca, I. doi  openurl
  Title Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques Type
  Year 2019 Publication Algorithmica Abbreviated Journal Algorithmica  
  Volume 81 Issue 3 Pages 986-1005  
  Keywords FPT algorithms; Treewidth; Potential maximal cliques  
  Abstract Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54-87, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.  
  Address (up) [Liedloff, Mathieu; Todinca, Ioan] Univ Orleans, INSA Ctr Val Loire, LIFO, EA 4022, Orleans, France, Email: mathieu.liedloff@univ-orleans.fr;  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0178-4617 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000460105700003 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 989  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: