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

exact exponential algorithms to find tropical connected sets of minimum size

THEORETICAL COMPUTER SCIENCE 2017年 676卷 33-41页

作者： Chapelle, Mathieu Cochefert, Manfred Kratsch, Dieter Letourneur, Romain Liedloff, Mathieu Univ Libre Bruxelles CP 212 B-1050 Brussels Belgium Univ Lorraine LITA F-57045 Metz 01 France Univ Orleans INSA Ctr Val Loire LIFO F-45067 Orleans France

Tropical Connected Set is strongly related to the Graph Motif problem which deals with vertex-colored graphs. Graph Motif has various applications in biology and metabolic networks, and has widely been studied in the last twenty years. The input of the Tropical Connected Set problem is a vertex-colored graph (G, c), where G = (V, E) is a graph and c is a vertex coloring assigning to each vertex of G a color. The task is to find a connected subset S subset of V of minimum size such that each color of G appears in S. This problem is known to be NP-complete, even when restricted to trees of height at most three. We study exact exponential algorithms to solve Tropical Connected Set. We present an O*(1.5359(n)) time algorithm for general graphs and an O*(1.2721(n)) time algorithm for trees. We also show that Tropical Connected Set on trees has no sub-exponential algorithm unless the exponential Time Hypothesis fails. 2017 Elsevier B.V. All rights reserved.

关键词： algorithms Graphs exact exponential algorithms Colored graphs

来源：评论

学校读者我要写书评

暂无评论

exact and Approximate Digraph Bandwidth

引用

THEORY OF COMPUTING SYSTEMS 2025年第1期69卷 1-29页

作者： Jain, Pallavi Kanesh, Lawqueen Lochet, Willian Saurabh, Saket Sharma, Roohani Indian Inst Technol Jodhpur India Univ Montpellier CNRS LIRMM Montpellier France Inst Math Sci HBNI Chennai 600113 India Univ Bergen Bergen Norway

In this paper, we introduce a directed variant of the classical Bandwidthproblem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph DD and an ordering sigma sigma of its vertices, the digraph bandwidth of sigma sigma with respect to DD is equal to the maximum value of sigma(v)-sigma(u)over all arcs (u,v) of DD going forward along sigma sigma (that is, when sigma(u)sigma(u)algorithms for Digraph Bandwidth which have running times of the form 2(O(n)). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph DD, respectively. Digraph Bandwidth can be solved in O-star(3(n)center dot 2(m)) time. This result implies a 2(O(n)) time algorithm on sparse graphs, such as graphs of bounded average degree (planar graphs). Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most tt, then Digraph Bandwidth can be solved in time O-star(2(n+(t+2)logn)). This result implies a 2(n+O(root nlogn)) algorithm, for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph HH as a minor. Digraph Bandwidth can be solved in min{O-star(4(n)center dot b(n)),O-star(4(n)center dot 2(blogblogn))} time, where bb denotes the optimal digraph bandwidth of DD. This allow us to deduce a 2(O)(n) algorithm in many cases, for example when b <= nlog2n. Finally,

关键词： Directed bandwidth Approximation scheme exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving Target Set Selection with Bounded Thresholds Faster than 2ⁿ

引用

ALGORITHMICA 2023年第2期85卷 384-405页

作者： Bliznets, Ivan Sagunov, Danil Russian Acad Sci Steklov Inst Math St Petersburg Dept Fontanka River Embarkment 27 St Petersburg 191011 Russia

In this paper we consider the TARGET SET SELECTION problem. The problem naturally arises in many fields like economy, sociology, medicine. In the TARGET SET SELECTION problem one is given a graph G with a function thr:V(G)-> N boolean ORalgorithms and two integers k,l. The goal of the problem is to activate at most k vertices initially so that at the end of the activation process there are at least l activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever;(ii) a vertex v becomes activated if at least thr(v) of its neighbours are activated. The problem and its different special cases were extensively studied from the approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others. Despite the extensive study of the problem it is still unknown whether the problem can be solved in O*((2-epsilon)n) time for some epsilon>0. We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by l is W[1]-hard even when all thresholds are constant.

关键词： Target set selection exact exponential algorithms Vertex thresholds Social influence Irreversible conversions of graphs Bootstrap percolation

来源：评论

学校读者我要写书评

暂无评论

Quantum algorithms for One-Sided Crossing Minimization 32

Quantum Algorithms for One-Sided Crossing Minimization

引用

32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

作者： Caroppo, Susanna Da Lozzo, Giordano Di Battista, Giuseppe Roma Tre University Rome Italy

ISBN: (纸本)9783959773430

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for exponential-Time Dynamic Programming algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in O∗(1.728n) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in O∗(2n) time and polynomial space. © Susanna Caroppo, Giordano Da Lozzo, and Giuseppe Di Battista.

关键词： exact exponential algorithms One-sided crossing minimization quantum divide and conquer quantum dynamic programming quantum graph drawing

来源：评论

学校读者我要写书评

暂无评论

Parameterized and exact algorithms for finding a read-once resolution refutation in 2CNF formulas

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2022年第1期90卷 3-29页

作者： Subramani, K. Wojciechowski, Piotr West Virginia Univ LDCSEE Morgantown WV 26506 USA

In this paper, we discuss algorithms for the problem of finding read-once resolution refutations of unsatisfiable 2CNF formulas within the resolution refutation system. Broadly, a read-once resolution refutation is one in which each constraint (input or derived) is used at most once. Read-once resolution refutations have been widely studied in the literature for a number of constraint system-refutation system pairs. For instance, read-once resolution has been analyzed for boolean formulas in conjunctive normal form (CNF) and read-once cutting planes have been analyzed for polyhedral systems. By definition, read-once refutations are compact, and hence valuable in applications that place a premium on visualization. The satisfiability problem (SAT) is concerned with finding a satisfying assignment for a boolean formula in CNF. While SAT is NP-complete in general, there exist some interesting subclasses of CNF formulas, for which it is decidable in polynomial time. One such subclass is the class of 2CNF formulas, i.e., CNF formulas in which each clause has at most two literals. The existence of efficient algorithms for satisfiability checking in 2CNF formulas (2SAT), makes this class useful from the perspective of modeling selected logic programs. The work in this paper is concerned with the read-once refutability problem (under resolution) in this subclass. Although 2SAT is decidable in polynomial time, the problem of finding a read-once resolution refutation of an unsatisfiable 2CNF formula is NP-complete. We design non-trivial, parameterized and exact exponential algorithms for this problem. Additionally, we study the computational complexity of finding a shortest read-once resolution refutation of a 2CNF formula.

关键词： 2CNF Read-once resolution NP-hard exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for restricted subset feedback vertex set in chordal and split graphs

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Bai, Tian Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

The RESTRICTED SUBSET FEEDBACK VERTEX SET problem (R-SFVS) takes a graph G = (V, E), a terminal set T C V, an integer k as the input. The task is to determine whether there exists a subset S C V ⧵ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal , split graphs can be solved in 0(1.1550|V|) time and exponential space or in 0(1.1605|V|) time and polynomial space, significantly improving all previous results. As a by-product, we show that the MAXIMUM INDEPENDENT SET problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to VERTEX COVER, we obtain an 0*(1.2738k)-time parameterized algorithm and a tight 0(k2)-kernel for R-SFVS in chordal and split graphs.

关键词： Subset feedback vertex set Chordal graphs Split graphs exact exponential algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

exact and Parameterized algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs 17th

Exact and Parameterized Algorithms for Restricted Subset Fee...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Bai, Tian Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

ISBN: (纸本)9783031203497;9783031203503

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The task is to determine whether there exists a subset S subset of V \ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to chordal graphs. In this paper, we show that R-SFVS in chordal graphs can be solved in time O(1.1550 vertical bar V vertical bar), significantly improving all the previous results. As a by-product, we prove that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover, we obtain a 1.2738(k)vertical bar V vertical bar(O(1))-time parameterized algorithm and an O(k(2))-kernel for R-SFVS in chordal graphs.

关键词： Subset feedback vertex set Chordal graphs exact exponential algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

FROM INDEPENDENT SETS AND VERTEX COLORINGS TO ISOTROPIC SPACES AND ISOTROPIC DECOMPOSITIONS: ANOTHER BRIDGE BETWEEN GRAPHS AND ALTERNATING MATRIX SPACES

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 924-971页

作者： Bei, Xiaohui Chen, Shiteng Guan, Ji Qiao, Youming Sun, Xiaoming Nanyang Technol Univ Sch Phys & Math Sci Singapore 637371 Singapore Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Univ Technol Sydney Ctr Quantum Software & Informat Parramatta NSW 2150 Australia Chinese Acad Sci Inst Comp Technol Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109-117;G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717-763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.

关键词： independent set vertex coloring alternating matrix spaces isotropic space isotropic decomposition exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Enumeration and maximum number of maximal irredundant sets for chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 265卷 69-85页

作者： Golovach, Petr A. Kratsch, Dieter Liedloff, Mathieu Sayadi, Mohamed Yosri Univ Bergen Dept Informat N-5020 Bergen Norway Univ Lorraine LITA Metz France Univ Orleans INSA Ctr Val de Loire LIFO EA 4022 FR-45067 Orleans France

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of an n-vertex chordal graph is at most 1.7549(n), and these can be enumerated in time 0(1.7549(n)). For interval graphs, we achieve the better upper bound of 1.6957(n) for the number of maximal irredundant sets and we show that they can be enumerated in time 0(1.6957(n)). Finally, we show that an n-vertex forest has at most 1.6181(n) maximal irredundant sets that can be enumerated in time 0(1.6181(n)). We complement the latter result by providing a family of forests having at least 1.5292(n) maximal irredundant sets. (C) 2019 Elsevier B.V. All rights reserved.

关键词： exact exponential algorithms Enumeration Maximal irredundant sets Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

Enumeration and maximum number of minimal dominating sets for chordal graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期783卷 41-52页

作者： Golovach, Petr A. Kratsch, Dieter Liedtoff, Mathieu Sayadi, Mohamed Yosri Univ Bergen Dept Informat N-5020 Bergen Norway Univ Lorraine LITA Metz France Univ Orleans INSA Ctr Val de Loire LIFO EA 4022 FR-45067 Orleans France

We study the enumeration of the minimal dominating sets and upper bounds for the number of such sets in chordal graphs. We show that the maximum number of minimal dominating sets of an n-vertex chordal graph is at most 1.5048(n) and prove that these sets can be enumerated in time O(1.5048(n)). In this way we improve the previous upper bound of 1.5214(n), recently established by Abu-Khzam and Eleggernes, and narrow the gap between the upper bound and the known lower bound of 1.4422(n). (C) 2019 Elsevier B.V. All rights reserved.

关键词： exact exponential algorithms Enumeration Minimal dominating sets Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：