|   | 
Details
   web
Records
Author Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K.
Title Complexity of splits reconstruction for low-degree trees Type
Year (up) 2015 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 180 Issue Pages 89-100
Keywords Reconstruction of trees; Computational complexity; Computational chemistry
Abstract Given a vertex-weighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NP-complete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NP-complete when T is required to be a path, the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NP-complete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixed-parameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physico-chemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved.
Address [Gaspers, Serge] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia, Email: sergeg@cse.unsw.edu.au;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000346545500009 Approved
Call Number UAI @ eduardo.moreno @ Serial 433
Permanent link to this record
 

 
Author Liedloff, M.; Montealegre, P.; Todinca, I.
Title Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques Type
Year (up) 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 [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