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

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

来源：评论

学校读者我要写书评

暂无评论

Enumerating Minimal Subset Feedback Vertex Sets

引用

ALGORITHMICA 2014年第1期69卷 216-231页

作者： Fomin, Fedor V. Heggernes, Pinar Kratsch, Dieter Papadopoulos, Charis Villanger, Yngve Univ Bergen Dept Informat N-5008 Bergen Norway Univ Paul Verlaine LITA Metz France Univ Ioannina Dept Math GR-45110 Ioannina Greece

The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and SaS dagger V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 (n) ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 (n) ).

关键词： exact exponential algorithms NP-hard problems Subset feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

MP or not MP: that is the question

引用

JOURNAL OF SCHEDULING 2016年第1期19卷 33-42页

作者： Della Croce, Federico Politecn Torino DAI Turin Italy CNR IEIIT I-10126 Turin Italy

It is well known that in the twentieth century, mathematical programming (MP) modeling and particularly linear programming (LP) modeling, even though strongly applied to combinatorial optimization, were not too successful when directed to scheduling problems. The purpose of this paper is to show that the field of successful applications of LP/MP modeling is still growing and includes also scheduling topics. We first focus on single machine scheduling. We consider a single machine scheduling model where a quadratic programming (QP) formulation handled by means of a QP solver is shown to be competitive with the state of the art approaches. Also, we discuss a single machine bicriterion scheduling problem and show that a standard LP formulation based on positional completion times performs reasonably well when handled by means of a LP solver. Then, we show how LP can be used to tighten bounds for approximation results in sequencing problems. Finally, we show how to enhance the complexity bounds of branch-and-reduce exact exponential algorithms by means of the so-called measure-and-conquer paradigm requiring always the solution of a specific MP model.

关键词： Modeling Machine scheduling Approximation exact exponential algorithms

来源：评论

学校读者我要写书评

暂无评论

Enumerating minimal connected dominating sets in graphs of bounded chordality

引用

THEORETICAL COMPUTER SCIENCE 2016年 630卷 63-75页

作者： Golovach, Petr A. Heggernes, Pinar Kratsch, Dieter Univ Bergen Dept Informat N-5020 Bergen Norway Univ Lorraine LITA Metz France

Enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O (1.7159(n)), of split graphs in time 0(1.3803(n)), and of AT-free, strongly chordal, and distance-hereditary graphs in time 0*(3(n/3)), where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes. (C) 2016 Elsevier B.V. All rights reserved.

关键词： exact exponential algorithms Enumeration Minimal connected dominating sets

来源：评论

学校读者我要写书评

暂无评论

Largest Chordal and Interval Subgraphs Faster than

引用

ALGORITHMICA 2016年第2期76卷 569-594页

作者： Bliznets, Ivan Fomin, Fedor V. Pilipczuk, Michal Villanger, Yngve St Petersburg Dept Steklov Inst Math 27 Fontanka St Petersburg Russia Univ Bergen Dept Informat Bergen Norway Univ Warsaw Inst Informat Warsaw Poland

We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time for some . These are the first algorithms breaking the trivial bound of the bru... 详细信息

关键词： exact exponential algorithms Chordal graphs Interval graphs Maximum induced Pi-subgraph

来源：评论

学校读者我要写书评

暂无评论

Branch and Recharge: exact algorithms for Generalized Domination

引用

ALGORITHMICA 2011年第2期61卷 252-273页

作者： Fomin, Fedor V. Golovach, Petr A. Kratochvl, Jan Kratsch, Dieter Liedloff, Mathieu Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France Univ Bergen Dept Informat N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Charles Univ Prague Dept Appl Math CR-11800 Prague 1 Czech Republic Charles Univ Prague Inst Theoret Comp Sci CR-11800 Prague 1 Czech Republic Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

In this paper we present branching algorithms for infinite classes of problems. The novelty in the design and analysis of our branching algorithms lies in the fact that the weights are redistributed over the graph by the algorithms. Our particular setting to make this idea work is a combination of a branching approach with a recharging mechanism. We call it Branch & Recharge. To demonstrate this approach we consider a generalized domination problem. Let sigma and I +/- be two nonempty sets of nonnegative integers. A vertex subset SaS dagger V of an undirected graph G=(V(G),E(G)) is called a (sigma,I +/-)-dominating set of G if |N(v)a (c) S|a sigma for all vaS and |N(v)a (c) S|aI +/- for all vaVa-S. This notion generalizes many domination-type graph invariants. We present Branch & Recharge algorithms enumerating all (sigma,I +/-)-dominating sets of an input graph G in time O (*)(c (n) ) for some c < 2, if sigma is successor-free, i.e., it does not contain two consecutive integers, and either both sigma and I +/- are finite, or one of them is finite and sigma a (c) I +/-=a.... Our algorithm implies a non trivial upper bound of O (*)(c (n) ) on the number of (sigma,I +/-)-dominating sets in an n-vertex graph under the above conditions on sigma and I +/-.

关键词： exact exponential algorithms NP-hard problems Generalized domination Branch and recharge

来源：评论

学校读者我要写书评

暂无评论

Bicolored independent sets and bicliques

引用

INFORMATION PROCESSING LETTERS 2012年第8-9期112卷 329-334页

作者： Couturier, Jean-Francois Kratsch, Dieter Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France

We introduce the decision problem BICOLORED INDEPENDENT SET which generalizes the well-known NP-complete graph problem INDEPENDENT SET. We present an O(1.2691(n)) time algorithm solving its counting analogue #BICOLORED INDEPENDENT SET. We show how to use this algorithm to establish algorithms solving biclique counting problems and provide an O(1.2691(n)) time algorithm solving *BIPARTITE BICLIQUE and an O(1.6107(n)) time algorithm solving #NON-INDUCED BICLIQUE. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithms exact exponential algorithms Independent set Biclique

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：