检索结果-内蒙古大学图书馆

On structural parameterization and molecular modeling of peptide analogues by molecular electronegativity edge vector (VMEE): Estimation and prediction for biological activity of dipeptides

引用

JOURNAL OF THE CHINESE CHEMICAL SOCIETY 2001年第5期48卷 937-944页

作者： Li, SZ Fu, BH Wang, YQ Liu, SS Chongqing Univ Coll Environm & Chem & Chem Engn Chongqing 400044 Peoples R China Chongqing Univ Inst Biol Engn Chongqing 400044 Peoples R China Guilin Inst Technol Dept Appl Chem Guilin 541004 Peoples R China

Based on the distance between atoms and the electro-negativity of each atom, a new set of descriptors called the molecular electronegativity edge vector (VMEE) being applied to describe the molecular structure of peptide analogues, is proposed only from the primary structure of peptides. Here several quantitative structure activity relationship models are proposed on the biological activity of 58 angiotensin converting enzyme (ACE) inhibitors and of 47 bitter tasting dipeptides by multiple linear regression method. The results show that the novel molecular electronegativity edge vector (VMEE) has both excellent structural selectivity and good activity estimation. Besides, this novel molecular electronegative edge vector, because it is easy to calculate, will be useful in structure characterization and activity prediction of biological molecules.

关键词： molecular electronegativity edge vector (VMEE) structural parameterization molecular modeling peptide analogues dipeptide quantitative structure activity relationship (QSAR)

来源：评论

学校读者我要写书评

暂无评论

Comparison of structural parameterization methods for the multidisciplinary optimization of active morphing wing sections

引用

COMPUTERS & STRUCTURES 2022年 263卷 106743-106743页

作者： Dexl, Florian Hauffe, Andreas Wolf, Klaus Tech Univ Dresden Inst Aerosp Engn D-01062 Dresden Germany

Morphing wings promise to increase the aerodynamic efficiency of future aircraft. A challenging task is to find structures that enable the active deformation of morphing wings leading to an increased aerodynamic efficiency and being lightweight at the same time. For the development of suitable optimization methods, choosing an efficient topology parameterization method is a crucial point. Contrary demands are a small number of design variables and a wide description of valid structures. The present work compares three different parameterization methods for their applicability in the multidisciplinary multi objective optimization of active morphing wing sections. Namely, these parameterization methods are Lindenmayer cellular systems, Voronoi diagrams and the bijective graph representation. It is shown that all three parameterization methods are basically suitable for the optimization problem addressed but have individual characteristics and benefits. CO 2022 Elsevier Ltd. All rights reserved.

关键词： Morphing wing section structural parameterization Evolutionary optimization Lindenmayer cellular system Voronoi diagram Bijective graph representation

来源：评论

学校读者我要写书评

暂无评论

structural parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization

引用

ALGORITHMICA 2018年第9期80卷 2683-2724页

作者： Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Madras Tamil Nadu India

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the 'deletion set'. In this paper, we show that FVS is fixed-parameter tractable by an time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time is not possible unless SETH fails. When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an time algorithm. When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an algorithm. When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an vertices kernel improving from the previously known bound. When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with vertices. We also prove a lower bound of size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.

关键词： Parameterized complexity Kernelization Feedback vertex set structural parameterization W-hardness

来源：评论

学校读者我要写书评

暂无评论

structural parameterizations of Tracking Paths problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 934卷 91-102页

作者： Choudhary, Pratibha Raman, Venkatesh Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic HBNI Inst Math Sci Chennai India

Given a graph G with source and destination vertices s, t E V (G) respectively, TRACKING PATHS asks for a minimum set of vertices T c V (G), such that the sequence of vertices restricted to T encountered in each simple path from s to t is unique. The problem was proven NP-hard [3] and was found to admit a quadratic kernel when parameterized by the size of the desired solution [8]. Following recent trends, for the first time, we study TRACKING PATHS with respect to structural parameters of the input graph, parameters that measure how far the input graph is, from an easy instance. We prove that TRACKING PATHS admits fixed-parameter tractable (FPT) algorithms when parameterized by the following parameters: (i) size of a 2-dominating set, (ii) size of cluster vertex deletion set, and (iii) size of split deletion set. En route we also look at VERTEX COVER parameterized by the size of edge clique cover and show it fixed-parameter tractable.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Tracking Paths structural parameterization Vertex cover Cluster vertex deletion set Undirected graphs Split graphs Edge clique cover

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of dominating set variants in almost cluster and split graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 150卷

作者： Goyal, Dishant Jacob, Ashwin Kumar, Kaushtubh Majumdar, Diptapriyo Raman, Venkatesh Indian Inst Technol Delhi New Delhi India Natl Inst Technol Calicut Calicut India Mentor G Corp Noida India Indraprastha Inst Informat Technol Delhi New Delhi India HBNI Inst Math Sci Chennai India

We consider structural parameterizations of several variants of DOMINATING SET in the parameter ecology program. We give improved FPT algorithms and lower bounds under well-known conjectures for DOMINATING SET and its variants in graphs that are k vertices away from a cluster graph or a split graph. These are graphs in which there is a set of k vertices (called the modulator) whose deletion results in a cluster graph or a split graph. We also call k as the deletion distance (to the appropriate class of graphs). For example, we show that when parameterized by the deletion distance k to cluster graphs: DOMINATING SET, INDEPENDENT DOMINATING SET, DOMINATING CLIQUE, EFFICIENT DOMINATING SET and TOTAL DOMINATING SET can be solved in 3knO(1)-time. Additionally, when parameterized by the deletion distance k to split graphs, we prove that EFFICIENT DOMINATING SET can be solved in 3k/2nO(1)-time breaking the 2k barrier. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Parameterized complexity Domination problems structural parameterization Set cover with partition Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Polynomial kernels for hitting forbidden minors under structural parameterizations

引用

THEORETICAL COMPUTER SCIENCE 2020年 841卷 124-166页

作者： Jansen, Bart M. P. Pieterse, Astrid Eindhoven Univ Technol POB 513 NL-5600 MB Eindhoven Netherlands Humboldt Univ Dept Comp Sci Berlin Germany

We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graph F, the the F-DELETION problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when T contains a planar graph, an instance (G, k) can be reduced in polynomial time to an equivalent one of size k(O(1)). In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-DELETION problem by the size of a vertex modulator whose removal results in a graph of constant treedepth eta. We prove that for each set F of connected graphs and constant eta, the F-DELETION problem parameterized by the size of a treedepth-eta modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-DELETION. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G - X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-DELETION solution from a single connected component of G - X. By bounding the number of different types of behavior that can occur by a polynomial in vertical bar X vertical bar, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-DELETION Such as VERTEX COVER and FEEDBACK VERTEX SET. It also generalizes earlier prepr

关键词： Kernelization F-minor free deletion Treedepth modulator structural parameterization

来源：评论

学校读者我要写书评

暂无评论

A Turing kernelization dichotomy for structural parameterizations of F-Minor-Free Deletion

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 119卷 164-182页

作者： Donkers, Huib Jansen, Bart M. P. Eindhoven Univ Technol POB 513 NL-5600 MB Eindhoven Netherlands

For a fixed finite family of graphs F, the F-MINOR-FREE DELETION problem takes as input a graph G and integer t and asks whether a size-t vertex set X exists such that G - X is F-minor-free. {K-2}-MINOR-FREE DELETION and {K-3}-MINOR-FREE DELETION encode VERTEX COVER and FEEDBACK VERTEX SET respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. We show {P-3}-MINOR-FREE DELETION parameterized by the feedback vertex number is MK[2]-hard. This rules out the existence of a polynomial kernel assuming NP not subset of coNP/poly. Our hardness result generalizes to any F containing only graphs with a connected component of at least 3 vertices, using as parameter the vertex-deletion distance to treewidth min tw(F), where min tw(F) denotes the minimum treewidth of the graphs in F. For all other families F we present a polynomial Turing kernelization. Our results extend to F-SUBGRAPH-FREE DELETION. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： Kernelization Turing kernelization Minor-free deletion Subgraph-free deletion structural parameterization

来源：评论

学校读者我要写书评

暂无评论

BRIDGE-DEPTH CHARACTERIZES WHICH MINOR-CLOSED structural parameterizationS OF VERTEX COVER ADMIT A POLYNOMIAL KERNEL*

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2022年第4期36卷 2737-2773页

作者： Bougeret, Marin Jansen, Bart M. P. Sau, Ignasi Univ Montpellier LIRMM F-34095 Montpellier France Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Univ Montpellier CNRS LIRMM F-34095 Montpellier France

We study the kernelization complexity of structural parameterizations of the Vertex Cover problem. Here, the goal is to find a polynomial-time preprocessing algorithm that can reduce any instance (G, k) of the Vertex Cover problem to an equivalent one, whose size is polynomial in the size of a predetermined complexity parameter of G. A long line of previous research deals with parameterizations based on the number of vertex deletions needed to reduce G to a member of a simple graph class F, such as forests, graphs of bounded tree-depth, and graphs of maximum degree two. We set out to find the most general graph classes F for which Vertex Cover parameterized by the vertex-deletion distance of the input graph to F admits a polynomial kernelization. We give a complete characterization of the minor-closed graph families F for which such a kernelization exists. We introduce a new graph parameter called bridge-depth, and prove that a polynomial kernelization exists if and only if F has bounded bridge-depth. The proof is based on an interesting connection between bridge-depth and the size of minimal blocking sets in graphs, which are vertex sets whose removal decreases the independence number.

关键词： vertex cover parameterized complexity polynomial kernel structural parameterization bridge-depth

来源：评论

学校读者我要写书评

暂无评论

A Turing Kernelization Dichotomy for structural parameterizations of F-Minor-Free Deletion 1

引用

45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Donkers, Huib Jansen, Bart M. P. Eindhoven Univ Technol POB 513 NL-5600 MB Eindhoven Netherlands

ISBN: (数字)9783030307868

ISBN: (纸本)9783030307868;9783030307851

For a fixed finite family of graphs F, the F-MINOR-FREE DELETION problem takes as input a graph G and an integer l and asks whether there exists a set X subset of V (G) of size at most l such that G - X is F-minor-free. For F = {K-2} and F = {K-3} this encodes VERTEX COVER and FEEDBACK VERTEX SET respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. Such a polynomial kernelization also exists for any F containing a planar graph but no forests. In this paper we show that F-MINOR-FREE DELETION parameterized by the feedback vertex number is MK[2]-hard for F = {P-3}. This rules out the existence of a polynomial kernel assuming NP not subset of coNP/poly, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any F not containing a P-3-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth min tw(F), where min tw(F) denotes the minimum treewidth of the graphs in F. For the other case, where F contains a P-3-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to F-SUBGRAPH-FREE DELETION.

关键词： Turing kernelization Minor-free deletion Subgraph-free deletion structural parameterization

来源：评论

学校读者我要写书评

暂无评论

On structural parameterizations of Node Kayles 1

引用

21st Japanese Conference, JCDCGGG

作者： Kobayashi, Yasuaki Kyoto Univ Sakyo Ku Kyoto 6068501 Japan

ISBN: (数字)9783030900489

ISBN: (纸本)9783030900489;9783030900472

Node Kayles is a well-known two-player impartial game on graphs: Given an undirected graph, each player alternately chooses a vertex not adjacent to previously chosen vertices, and a player who cannot choose a new vertex loses the game. The problem of deciding if the first player has a winning strategy in this game is known to be PSPACE-complete. A few researches on algorithmic aspects of Node Kayles have been done so far. In this paper, we consider the problem from the view point of fixed-parameter tractability. We show that the problem is fixed-parameter tractable parameterized by the size of a minimum vertex cover or the modular-width of the given graph.

关键词： Fixed-parameter tractability Node Kayles structural parameterization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：