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

SIAM International Conference on Data Mining (SDM)

作者： Kloster, Kyle Sullivan, Blair D. Van der Poel, Andrew North Carolina State Univ Raleigh NC 27695 USA

ISBN: (纸本)9781611975673

Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these dense substructures is often a complete bipartite graph (biclique), and the problem requires enumerating all maximal bicliques (instead of identifying just the largest or densest). The best known algorithm in general graphs is due to Dias et al., and runs in time O(M vertical bar V vertical bar(4)), where M is the number of maximal induced bicliques (MIBs) in the graph. When the graph being searched is itself bipartite, Zhang et al. give a faster algorithm where the time per MIB depends on the number of edges in the graph. In this work, we present a new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is. Specifically, the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartite graph. Our algorithm runs in time O(M vertical bar V parallel to E vertical bar k(2)3(k/3)), which is an improvement on Dias et al. whenever k <= 3 log(3) vertical bar V vertical bar. We implement our algorithm alongside a variant of Dias et al.'s in open-source C++ code, and experimentally verify that the OCT-based approach is faster in practice on graphs with a wide variety of sizes, densities, and OCT decompositions.

关键词： bicliques odd cycle transversal parameterized algorithms enumeration bipartite

来源：评论

学校读者我要写书评

暂无评论

Complexity and parameterized algorithms for Cograph Editing

引用

THEORETICAL COMPUTER SCIENCE 2012年 461卷 45-54页

作者： Liu, Yunlong Wang, Jianxin Guo, Jiong Chen, Jianer Cent South Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Hunan Normal Univ Sch Math & Comp Sci Changsha 410013 Hunan Peoples R China Univ Saarland D-66123 Saarbrucken Germany Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Cograph Editing is to find for a given graph G = (V, E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612(k) + vertical bar V vertical bar(4.5)), which improves the trivial algorithm of running time O(6(k) + vertical bar V vertical bar(4-5)). (c) 2011 Elsevier B.V. All rights reserved.

关键词： Cograph Editing NP-hardness parameterized algorithms P-4-sparse graph

来源：评论

学校读者我要写书评

暂无评论

parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices 35

Parameterized Approximation Schemes for Steiner Trees with S...

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Dvorak, Pavel Feldmann, Andreas Emil Knop, Dusan Masarik, Tomas Toufar, Tomas Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Charles Univ Prague Dept Appl Math Prague Czech Republic Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783959770620

We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand STEINER TREE is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of STEINER TREE, such as DIRECTED STEINER TREE and STEINER FOREST. For neither of these an EPAS is likely to exist for the studied parameter: for STEINER FOREST an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For DIRECTED STEINER TREE we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for UNWEIGHTED DIRECTED STEINER TREE. Also we prove that there is an EPAS and a PSAKS for STEINER FOREST if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.

关键词： Steiner Tree Steiner Forest Approximation algorithms parameterized algorithms Lossy Kernelization

来源：评论

学校读者我要写书评

暂无评论

Complexity of Secure Sets

引用

ALGORITHMICA 2018年第10期80卷 2909-2940页

作者： Bliem, Bernhard Woltran, Stefan TU Wien Inst Informat Syst 184 2 Favoritenstr 9-11 A-1040 Vienna Austria

A secure set S in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.

关键词： Secure set Complexity analysis parameterized complexity Treewidth parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations

引用

Electronic Notes in Theoretical Computer Science 2019年 346卷 655-666页

作者： Farley Soares Oliveira Hidefumi Hiraishi Hiroshi Imai Department of Computer Science The University of Tokyo Tokyo Japan

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O* (2 pw 2 /4+ o (pw 2 ) ) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O* (2 bw 2 /2+o(bw 2 ) ) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

关键词： Acyclic Orientations Totally Cyclic Orientations parameterized algorithms FPT algorithms Path-width Branch-width Binary Decision Diagram

来源：评论

学校读者我要写书评

暂无评论

Default Logic and Bounded Treewidth 1

引用

12th International Conference on Language and Automata Theory and Applications (LATA)

作者： Fichte, Johannes K. Hecher, Markus Schindler, Irina Tech Univ Wien Vienna Austria Leibniz Univ Hannover Hannover Germany

ISBN: (数字)9783319773131

ISBN: (纸本)9783319773131;9783319773124

In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (ExT). Our algorithm can even be used to enumerate all generating defaults (ENuMSE) that lead to stable extensions. We show that our algorithm decides EXT in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves ENuMSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.

关键词： parameterized algorithms Tree decompositions Dynamic programming Reiter's default logic Propositional logic

来源：评论

学校读者我要写书评

暂无评论

Exploiting Treewidth for Projected Model Counting and Its Limits 21st

Exploiting Treewidth for Projected Model Counting and Its Li...

引用

21st International Conference on Theory and Applications of Satisfiability Testing (SAT) Held as Part of the Federated Logic Conference (FloC)

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Woltran, Stefan TU Wien Inst Log & Computat Vienna Austria

ISBN: (纸本)9783319941448;9783319941431

In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projected variables, where multiple solutions that are identical when restricted to the projected variables count as only one solution. Our algorithm exploits small treewidth of the primal graph of the input instance. It runs in time O(2(2k+4) n(2)) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm.

关键词： parameterized algorithms Tree decompositions Multi-pass dynamic programming Projected model counting Propositional logic

来源：评论

学校读者我要写书评

暂无评论

Locating the Eigenvalues for Graphs of Small Clique-Width 13th

Locating the Eigenvalues for Graphs of Small Clique-Width

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Furer, Martin Hoppen, Carlos Jacobs, David P. Trevisan, Vilmar Penn State Univ Dept Comp Sci & Engn State Coll PA 16801 USA Univ Fed Rio Grande do Sul Inst Matemat Alegre Brazil Clemson Univ Sch Comp Clemson SC USA

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be co... 详细信息

ISBN: (纸本)9783319774046;9783319774039

关键词： Eigenvalues Clique-width Congruent matrices Efficient algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem 35

On Structural Parameterizations of the Bounded-Degree Vertex...

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Ganian, Robert Klute, Fabian Ordyniak, Sebastian TU Wien Algorithms & Complex Grp Vienna Austria FI MU Brno Czech Republic

ISBN: (纸本)9783959770620

We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve the main open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.

关键词： Bounded-degree Vertex Deletion Feedback Vertex Set parameterized algorithms Treecut Width

来源：评论

学校读者我要写书评

暂无评论

TREEWIDTH and PATHWIDTH parameterized by the vertex cover number

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part1期216卷 114-129页

作者： Chapelle, Mathieu Liedloff, Mathieu Todinca, Loan Villanger, Yngve Univ Paris Est Marne La Vallee IGM LabInfo 5 Bd Descartes Champs Sur Marne F-77454 Marne La Vallee 2 France Univ Orleans LIFO BP 6759 F-45067 Orleans 2 France Univ Bergen Dept Informat N-5020 Bergen Norway

After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3(k)) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover Number. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Treewidth Pathwidth Vertex cover parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：