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

An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

DISCRETE APPLIED MATHEMATICS 2015年 193卷 145-161页

作者： Komusiewicz, Christian Sorge, Manuel TU Inst Softwaretech & Theoret Informat Berlin Germany

We investigate the computational complexity of the DENSEST k-SUBGRAPH problem, where the input is an undirected graph G = (V, E) and one wants to find a subgraph on exactly k vertices with the maximum number of edges. We extend previous work on DENSEST k-SUBGRAPH by studying its parameterized complexity for parameters describing the sparseness of the input graph and for parameters related to the solution size k. On the positive side, we show that, when fixing some constant minimum density mu of the sought subgraph, DENSEST k-SUBGRAPH becomes fixed-parameter tractable with respect to either of the parameters maximum degree of G and h-index of G. Furthermore, we obtain a fixed-parameter algorithm for DENSEST k-SUBGRAPH with respect to the combined parameter "degeneracy of G and vertical bar V vertical bar - k". On the negative side, we find that DENSEST k-SUBGRAPH is W[1]-hard with respect to the combined parameter "solution size k and degeneracy of G". We furthermore strengthen a previous hardness result for DENSEST k-SUBGRAPH (Cai, 2008) by showing that for every fixed mu, 0 < mu < 1, the problem of deciding whether G contains a subgraph of density at least mu is W[1]-hard with respect to the parameter vertical bar V] - k. Our positive results are obtained by an algorithmic framework that can be applied to a wide range of fixed-CARDINALITY OPTIMIZATION problems. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Clique relaxations NP-hard problems fixed-parameter algorithms Subgraph enumeration

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity analysis for the Closest String with Wildcards problem

引用

THEORETICAL COMPUTER SCIENCE 2015年 600卷 11-18页

作者： Hermelin, Danny Rozenberg, Liat Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Haifa IL-31999 Haifa Israel

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity The closest string problem fixed-parameter algorithms Computational biology

来源：评论

学校读者我要写书评

暂无评论

Myhill-Nerode Methods for Hypergraphs

引用

ALGORITHMICA 2015年第4期73卷 696-729页

作者： van Bevern, Rene Downey, Rodney G. Fellows, Michael R. Gaspers, Serge Rosamond, Frances A. TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Victoria Univ Wellington Wellington New Zealand Charles Darwin Univ Sch Engn & IT Darwin NT 0909 Australia Univ New S Wales Sydney NSW Australia NICTA Sydney NSW Australia

We give an analog of the Myhill-Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testing whether a hypergraph has cutwidth at most that runs in linear time for constant . In terms of parameterized complexity theory, the problem is fixed-parameter linear parameterized by . (2) We show that it is not expressible in monadic second-order logic whether a hypergraph has bounded (fractional, generalized) hypertree width. The proof leads us to conjecture that, in terms of parameterized complexity theory, these problems are W[1]-hard parameterized by the incidence treewidth (the treewidth of the incidence graph). Thus, in the form of the Myhill-Nerode theorem for hypergraphs, we obtain a method to derive linear-time algorithms and to obtain indicators for intractability for hypergraph problems parameterized by incidence treewidth.

关键词： NP-hard problems fixed-parameter algorithms Automata theory Cutwidth Hypertree width

来源：评论

学校读者我要写书评

暂无评论

Towards an algorithmic guide to Spiral Galaxies

引用

THEORETICAL COMPUTER SCIENCE 2015年 586卷 26-39页

作者： Fertin, Guillaume Jamshidi, Shahrad Komusiewicz, Christian Univ Nantes LINA CNRS UMR 6241 F-44035 Nantes France TU Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany

We study the one-player game SPIRAL GALAXIES from an algorithmic viewpoint. SPIRAL GALAXIES has been shown to be NP-hard [6] more than a decade ago, but so far it seems that no one has dared exploring its algorithmic ... 详细信息

关键词： NP-hard problems fixed-parameter algorithms One-player game

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC algorithms FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1815-1836页

作者： Goyal, Prachi Misra, Neeldhara Panolan, Fahad Zehavi, Meirav Indian Inst Sci Bangalore 560012 Karnataka India Inst Math Sci Madras 600113 Tamil Nadu India Technion Israel Inst Technol Haifa Israel

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

关键词： r-dimensional matching set packing 3D-matching fixed-parameter algorithms representative sets iterative expansion

来源：评论

学校读者我要写书评

暂无评论

Generalized Set and Graph Packing Problems

Generalized Set and Graph Packing Problems

引用

作者： Romero, Jazmin University of Waterloo

学位级别：doctor

Many complex systems that exist in nature and societycan be expressed in terms of networks (e.g., social networks,communication networks, biological networks, Web graph, amongothers). Usually a node represents an entity while an edgerepresents an interaction between two entities. A community arisesin a network when two or more entities have common interests,e.g., related proteins, industrial sectors, groups of people,documents of a collection. There exist applications that model acommunity as a fixed graph H [98, 10, 119, 2, 142, 136].Additionally, it is not expected that an entity of the networkbelongs to only one community; that is, communities tend to sharetheir members. The community discovering or community detectionproblem consists on finding all communities in a given *** problem has been extensively studied from a practicalperspective [61, 137, 122, 116]. However, we believe that thisproblem also brings many interesting theoretical questions. Thus inthis thesis, we will address this problem using a more rigorousapproach. To that end, we first introduce graph problems that weconsider capture well the community discovering problem. Thesegraph problems generalize the classical H-Packing problem [88] intwo different ways. In the H-Packing with t-Overlap problem, thegoal is to find in a given graph G (the network) at least ksubgraphs (the communities) isomorphic to a member of a family ofgraphs H (the community models) such that each pair of subgraphsoverlaps in at most t vertices (the shared members). On the otherhand, in the H-Packing with t-Membership problem instead oflimiting the pairwise overlap, each vertex of G is contained in atmost t subgraphs of the solution. For both problems each member ofH has at most r vertices and m edges. An instance of the H-Packingwith t-Overlap and t-Membership problems corresponds to aninstance of the H-Packing problem for t = 0 and t = 1,respectively. We also restrict the overlap between the edges ofthe subgraphs

关键词： fixed-parameter algorithms kernelization set packing graph packing overlapping communities

来源：评论

学校读者我要写书评

暂无评论

SPLIT VERTEX DELETION meets VERTEX COVER: New fixed-parameter and exact exponential-time algorithms

引用

INFORMATION PROCESSING LETTERS 2013年第5-6期113卷 179-182页

作者： Cygan, Marek Pilipczuk, Marcin Univ Lugano IDSIA Lugano Switzerland Univ Warsaw Inst Informat PL-00325 Warsaw Poland

In the SPLIT VERTEX DELETION problem, given a graph G and an integer k, we ask whether one can delete k vertices from the graph G to obtain a split graph (i.e., a graph, whose vertex set can be partitioned into two sets: one inducing a clique and the second one inducing an independent set). In this paper we study exact (exponential-time) and fixed-parameter algorithms for SPLIT VERTEX DELETION. We show that, up to a factor quasipolynomial in k and polynomial in n, the SPLIT VERTEX DELETION problem can be solved in the same time as the well-studied VERTEX COVER problem. By plugging in the currently best fixed-parameter algorithm for VERTEX COVER due to Chen et al. [Theor. Comput Sci. 411 (40-42) (2010) 3736-3756], we obtain an algorithm that solves SPLIT VERTEX DELETION in time O(-1.2738(k)k(O(logk)) + n(3)). We show that all maximal induced split subgraphs of a given n-vertex graph can be listed in O(3(n/3) n(O(logn))) time. To achieve our goals, we prove the following structural result that may be of independent interest: for any graph G we may compute a family P of size n(O(logn)) containing partitions of V(C) into two parts, such that for any two disjoint sets X-C, X-I subset of V (G) where G[X-C] is a clique and G[X-I] is an independent set, there is a partition in P which contains all vertices of X-C on one side and all vertices of X-I on the other. Moreover, the family P can be enumerated in O(n(O(logn))) time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Graph algorithms fixed-parameter algorithms Split graphs Split vertex deletion Branching algorithm

来源：评论

学校读者我要写书评

暂无评论

parameterized and approximation algorithms for finding two disjoint matchings

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期556卷 85-93页

作者： Chen, Zhi-Zhong Fan, Ying Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

We first present a randomized fixed-parameter algorithm for the NP-hard problem of deciding if there are two matchings M-1 and M-2 in a given graph G such that vertical bar M-1 vertical bar+ vertical bar M-2 vertical bar is a given number k. The algorithm runs in O (2(k)k(m + n)) expected time and can be derandomized to run in O (2(2k+12 log2 (2k)) kn (m + n) time, where n (respectively, m) is the number of vertices (respectively, edges) in G. We then extend the algorithm to the weighted version of the problem. We further present a combinatorial approximation algorithm for the NP-hard problem of finding two disjoint matchings in a given edge-weighted graph G so that their total weight is maximized. The algorithm achieves an approximation ratio close to 0.76 and runs in O(m + n(3) alpha(n)) time, where alpha is the inverse Ackermann function. (C) 2014 Elsevier B.V. All rights reserved.

关键词： fixed-parameter algorithms Approximation algorithms Color-coding Universal sets Matchings

来源：评论

学校读者我要写书评

暂无评论

The constrained shortest common supersequence problem

引用

JOURNAL OF DISCRETE algorithms 2013年 21卷 11-17页

作者： Dondi, Riccardo Univ Bergamo Dipartimento Sci Umane Soc Via Donizetti 3 I-24129 Bergamo Italy

Shortest common supersequence and longest common subsequence are two widely used measures to compare sequences in different fields, from AI planning to Bioinformatics. Inspired by recently proposed variants of these two measures, we introduce a new version of the shortest common supersequence problem, where the solution is required to satisfy a given constraint on the number of occurrences of each symbol. First, we investigate the computational and approximation complexity of the problem, then we give a 3/2-approximation algorithm. Finally, we investigate the parameterized complexity of the problem, and we present a fixed-parameter algorithm. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Shortest common supersequence Approximation algorithms Computational complexity fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximum Disjoint Paths on Edge-Colored Graphs: Approximability and Tractability

引用

algorithms 2013年第1期6卷 1-11页

作者： Bonizzoni, Paola Dondi, Riccardo Pirola, Yuri Univ Milano Bicocca Dept Comp Syst & Commun Milan Italy Univ Bergamo Dept Humanities & Social Sci Via Donizzetti 3 Bergamo Italy

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant epsilon > 0, the problem is not approximable within factor c(1-epsilon), where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.

关键词： social networks disjoint paths fixed-parameter algorithms hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：