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

An exact exponential time algorithm for counting bipartite cliques

INFORMATION PROCESSING LETTERS 2012年第13期112卷 535-539页

作者： Kutzkov, Konstantin IT Univ Copenhagen Copenhagen Denmark

We present a simple exact algorithm for counting bicliques of given size in a bipartite graph on n vertices. We achieve running time of O(1.2491(n)), improving upon known exact algorithms for finding and counting bipa... 详细信息

关键词： Analysis of algorithms exact exponential time algorithms Counting bipartite cliques

来源：评论

学校读者我要写书评

暂无评论

New exact algorithms for the 2-constraint satisfaction problem

引用

THEORETICAL COMPUTER SCIENCE 2014年 526卷 18-27页

作者： Golovnev, Alexander Kutzkov, Konstantin NYU New York NY 10003 USA IT Univ Copenhagen Copenhagen Denmark

Many optimization problems can be phrased in terms of constraint satisfaction. In particular MAX-2-SAT and MAX-2-CSP are known to generalize many hard combinatorial problems on graphs. algorithms solving the problem exactly have been designed but the running time is improved over trivial brute-force solutions only for very sparse instances. Despite many efforts, the only known algorithm [28] solving MAX-2-CSP over n variables in less than O*(2(n)) steps uses exponential space. Several authors have designed algorithms with running time O*(2(nf(d))) where f : R+ -> (0, 1) is a slowly growing function and d is the average variable degree of the input formula. The current best known algorithm for MAX-2-CSP [25] runs in time O*(2(n(1-2/d+1))) and polynomial space. In this paper we continue this line of research and design new algorithms for the MAX-2-SAT and MAX-2-CSP problems. First, we present a general technique for obtaining new bounds on the running time of a simple algorithm for MAX-2-CSP analyzed with respect to the number of vertices from algorithms that are analyzed with respect to the number of constraints. The best known bound for the problem is improved to O*(2(n(1-3(d+1)))) for d >= 3. We further improve the bound for MAX-2-SAT, in particular for d >= 6 we achieve O*(2(n(1-3.677/d+1))). As a second result we present an algorithm with asymptotically better running time for the case when the input instance is not very sparse. Building on recent work of Feige and Kogan we derive an upper bound on the size of a vertex separator for graphs in terms of the average degree of the graph. We then design a simple algorithm solving MAX-2-CSP in time O*(2(cdn)), c(d) = 1-2 alpha ln d/d d for some alpha < 1 and d = o(n). (C) 2014 Elsevier B.V. All rights reserved.

关键词： exact exponential time algorithms Constraint satisfaction Maximum satisfiability

来源：评论

学校读者我要写书评

暂无评论

Faster exact algorithms for some terminal set problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 88卷 195-207页

作者： Chitnis, Rajesh Fomin, Fedor V. Lokshtanov, Daniel Misra, Pranabendu Ramanujan, M. S. Saurabh, Saket Weizmann Inst Sci Fac Math & Comp Sci Rehovot Israel Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India

Many problems on graphs can be expressed in the following language: given a graph G = (V, E) and a terminal set T subset of V, find a minimum size set S subset of V which intersects all "structures" (such as cycles or paths) passing through the vertices in T. We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the O*(2(n)) barrier for the classic NODE MULTIWAY CUT, DIRECTED UNRESTRICTED NODE MULTIWAY CUT and DIRECTED SUBSET FEEDBACK VERTEX SET problems. (C) 2017 Elsevier Inc. All rights reserved.

关键词： exact exponential time algorithms Terminal set problems Multiway cut Feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

PATH CONTRACTION FASTER THAN 2ⁿ

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2020年第2期34卷 1302-1325页

作者： Agrawal, Akanksha Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Tale, Prafullkumar Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Bergen POB 7800 N-5020 Bergen Norway Univ Calif Santa Barbara Santa Barbara CA 93106 USA HBNI Inst Math Sci Chennai 600113 Tamil Nadu India UMI ReLax Chennai Tamil Nadu India

A graph G is contractible to a graph H if there is a set X subset of E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs the F-CONTRACTION problem takes as input a graph G on n vertices, and the objective is to output the largest integer t, such that G is contractible to a graph H is an element of F where vertical bar V(H)vertical bar = t. When F is the family of paths, then the corresponding .F-CONTRACTION problem is called PATH CONTRACTION. The problem PATH CONTRACTION admits a simple algorithm running in time 2(n). n(O(1)). In spite of the deceptive simplicity of the problem, beating the 2(n). n(O(1)) bound for PATH CONTRACTION seems quite challenging. In this paper, we design an exact exponential time algorithm for PATH CONTRACTION that runs in time 1.99987(n). n(O)((1)()). We also define a problem called 3-DISJOINT CONNECTED SUBGRAPHS and design an algorithm for it that runs in time 1.88(n). n(O(1)). The above algorithm is used as a subroutine in our algorithm for PATH CONTRACTION.

关键词： path contraction exact exponential time algorithms graph algorithms enumerating connected sets 3-disjoint connected subgraphs

来源：评论

学校读者我要写书评

暂无评论

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

引用

THEORY OF COMPUTING SYSTEMS 2013年第4期52卷 645-667页

作者： Couturier, Jean-Francois Golovach, Petr A. Kratsch, Dieter Liedloff, Mathieu Pyatkin, Artem Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.

关键词： algorithms Graphs exact exponential time algorithms Enumeration Counting Coloring

来源：评论

学校读者我要写书评

暂无评论

FASTER SPACE-EFFICIENT algorithms FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2018年第5期47卷 1755-1777页

作者： Bansal, Nikhil Garg, Shashwat Nederlof, Jesper Vyas, Nikhil Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 AB Eindhoven Netherlands MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k >= 2, random instances of k-sum can be solved using O(n(k-0.5) polylog(n)) time and O(log n) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n(2)) time algorithm if no value occurs too often in the same list.

关键词： space-efficient algorithms k-sum subset sum exact exponential time algorithms fine-grained complexity space-time trade-off exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

On Two Techniques of Combining Branching and Treewidth

引用

ALGORITHMICA 2009年第2期54卷 181-207页

作者： Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for MINIMUM MAXIMAL MATCHING and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.

关键词： exact exponential time algorithms Parameterized algorithms NP hard problems Treewidth #3-Coloring #Minimum dominating set Minimum maximal matching k-Weighted vertex cover

来源：评论

学校读者我要写书评

暂无评论

On Two Techniques of Combining Branching and Treewidth

On Two Techniques of Combining Branching and Treewidth

引用

17th International Symposium on algorithms and Computation (ISAAC 2006)

作者： Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

关键词： exact exponential time algorithms Parameterized algorithms NP hard problems Treewidth #3-Coloring #Minimum dominating set Minimum maximal matching k-Weighted vertex cover

来源：评论

学校读者我要写书评

暂无评论

Path contraction faster than 2n 46

Path contraction faster than 2n

引用

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

作者： Agrawal, Akanksha Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Tale, Prafullkumar Ben-Gurion University of the Negev Beersheba Israel University of Bergen Bergen Norway University of California Santa Barbara Santa BarbaraCA United States Institute of Mathematical Sciences HBNI and UMI ReLaX Chennai India Institute of Mathematical Sciences HBNI Chennai India

ISBN: (纸本)9783959771092

A graph G is contractible to a graph H if there is a set X ⊆ E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction problem takes as input a graph G on n vertices, and the objective is to output the largest integer t, such that G is contractible to a graph H ∈ F, where |V (H)| = t. When F is the family of paths, then the corresponding F-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time 2n · nO(1). In spite of the deceptive simplicity of the problem, beating the 2n · nO(1) bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time 1.99987n · nO(1). We also define a problem called 3-Disjoint Connected Subgraphs, and design an algorithm for it that runs in time 1.88n · nO(1). The above algorithm is used as a sub-routine in our algorithm for Path Contraction. © Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale;licensed under Creative Commons License CC-BY

关键词： 3-disjoint connected subgraphs Enumerating connected sets exact exponential time algorithms Graph algorithms Path contraction

来源：评论

学校读者我要写书评

暂无评论

Maximum: 收藏
分享
引用; SIAM Journal on Discrete Mathematics 2012年第4期26卷 1758-1780页; 作者： Sushmita Gupta Venkatesh Raman Saket Saurabh; We show that for a fixed rrr, the number of maximal r; We show that for a fixed $r$ , the number of maximal $r$; 关键词： maximal -regular subgraphs combinatorial upper and lower bounds exact exponential time algorithms 05C85 05C30 05D99; 来源：评论; 学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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