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

An exponential time 2-approximation algorithm for bandwidth

THEORETICAL COMPUTER SCIENCE 2013年 511卷 23-31页

作者： Fuerer, Martin Gaspers, Serge Kasiviswanathan, Shiva Prasad Penn State Univ University Pk PA 16802 USA Univ New S Wales Sydney NSW Australia NICTA Sydney NSW Australia Gen Elect Res San Ramon CA USA

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b. In this paper, we present a 2-approximation algorithm for the Bandwidth problem that takes worst-case O(1.9797(n)) = O(3(0.6217n)) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have O*(3(n)) and O*(2(n)) worst-case running time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident to vertices in the same bucket or to vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a divide-and-conquer strategy along with dynamic programming to achieve the improved time bound. (C) 2013 Elsevier B.V. All rights reserved.

关键词： exponential time algorithm Approximation algorithm Graph bandwidth Bucket decomposition

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Non-separating Trees and Branchings in Digraphs

引用

algorithmICA 2016年第1期76卷 279-296页

作者： Bang-Jensen, Jorgen Saurabh, Saket Simonsen, Sven Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Inst Math Sci Madras Tamil Nadu India

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer , we can test whether D contains arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc-Disjoint Branchings and Non-Disconnecting Out-Branching. In Arc-Disjoint Branchings (Non-Disconnecting Out-Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. Non-Disconnecting Out-Branching is fixed parameter tractable (FPT) and admits a linear vertex kernel. Arc-Disjoint Branchings is FPT on strong digraphs.

关键词： Branching Spanning tree Fixed parameter tractable Parameterized complexity Linear vertex kernel exponential time algorithm Partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Computing branchwidth via efficient triangulations and blocks

引用

DISCRETE APPLIED MATHEMATICS 2009年第12期157卷 2726-2736页

作者： Fomin, Fedor V. Mazoit, Frederic Todinca, Ioan Univ Bordeaux LaBRI F-33405 Talence France Univ Bergen Dept Informat N-5020 Bergen Norway Univ Orleans LIFO F-45067 Orleans 2 France

Minimal triangulations and potential maximal cliques are the main ingredients for a number of polynomial time algorithms on different graph classes computing the treewidth of a graph. Potential maximal cliques are also the main engine of the fastest so far, exact (exponential) treewidth algorithm. Based on the recent results of Mazoit, we define the structures that can be regarded as minimal triangulations and potential maximal cliques for branchwidth: efficient triangulations and blocks. We show how blocks can be used to construct an algorithm computing the branchwidth of a graph on n vertices in time (2 root 3)(n) . n(0(1)). (C) 2009 Published by Elsevier B.V.

关键词： Graph Branchwidth exponential time algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction

引用

THEORY OF COMPUTING SYSTEMS 2015年第2期57卷 426-443页

作者： Sakai, Takayuki Seto, Kazuhisa Tamaki, Suguru Kyoto Univ Sakyo Ku Kyoto 6068501 Japan Seikei Univ Musashino Tokyo 1808633 Japan

We present a moderately exponential time and polynomial space algorithm for sparse instances of Max SAT. Our algorithms run in time of the form for instances with n variables and cn clauses. Our deterministic and randomized algorithm achieve and respectively. Previously, an exponential space deterministic algorithm with was shown by Dantsin and Wolpert [SAT 2006] and a polynomial space deterministic algorithm with was shown by Kulikov and Kutzkov [CSR [2007]]. Our algorithms have three new features. They can handle instances with (1) weights and (2) hard constraints, and also (3) they can solve counting versions of Max SAT. Our deterministic algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam. Our randomized algorithm uses random restriction instead of greedy restriction.

关键词： exponential time algorithm Polynomial space Weight Hard constraint Counting

来源：评论

学校读者我要写书评

暂无评论

A Randomized algorithm for 3-SAT

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第4期3卷 421-431页

作者： Ghosh, Subhas Kumar Misra, Janardan Honeywell Technol Solut 151-1DoraisanipalyaBannerghatta Rd Bangalore 560076 Karnataka India

In this work we propose and analyze a simple randomized algorithm for 3-SAT (i.e. an algorithm to find a satisfiable assignment for a Boolean formula in conjunctive normal form (CNF) having at most 3 literals in every clause). Given a k-CNF formula phi on n variables, and alpha is an element of {0, 1}(n) that satisfies phi, a clause of phi is critical if exactly one literal of that clause is satisfied under assignment alpha. Paturi et al. (Chicago J. Theor. Comput. Sci. 115, 1999) proposed a simple randomized algorithm (PPZ) for k-SAT for which success probability increases with the number of critical clauses (with respect to a fixed satisfiable solution of the input formula). Here, we first describe another simple randomized algorithm DEL which performs better if the number of critical clauses in input formula are less (with respect to a fixed satisfiable solution of the input formula). Subsequently, we combine these two simple algorithms such that the success probability of the combined algorithm is maximum of the success probabilities of PPZ and DEL on every input instance. We show that when the average number of clauses for a variable that appear as unique true literals in one or more critical clauses in phi is between 1 and 2/(3 center dot log (3/2)), combined algorithm performs better than the PPZ algorithm.

关键词： Boolean satisfiability Randomized algorithm exponential time algorithm Analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Reliability Calculation of P2P Streaming Systems with Bottleneck Links 31

Reliability Calculation of P2P Streaming Systems with Bottle...

引用

31st IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPS)

作者： Fujita, Satoshi Hiroshima Univ Dept Informat Engn Hiroshima Japan

ISBN: (纸本)9780769561493

Let G be a network with node set V and link set E, where each link e in E is associated with capacity c(e) and failure probability p(e). Let D = (s, t, d) be a flow demand on G which requests that a video stream of bit rate d should be delivered from source node s to sink node t through network G. The reliability of network G with respect to flow demand D is the probability of surviving a subgraph of G which admits D under the probabilistic link failures determined by function p. This paper shows that if G contains a constant number of bottleneck links and if the given video stream is divided into constant number of sub-streams, we can calculate the reliability of G in O(2(alpha vertical bar E vertical bar)vertical bar V vertical bar vertical bar E vertical bar) time, where alpha vertical bar E vertical bar is the number of links in the maximum connected component obtained by removing bottleneck links. This is a significant improvement of a naive method which takes O(2(vertical bar E vertical bar)vertical bar V vertical bar vertical bar E vertical bar) time.

关键词： Flow network reliability NP-hardness exponential time algorithm

来源：评论

学校读者我要写书评

暂无评论

A faster algorithm for finding maximum independent sets in sparse graphs

A faster algorithm for finding maximum independent sets in s...

引用

7th Latin American Symposium on Theoretical Informatics (LATIN 2006)

作者： Fürer, M Penn State Univ University Pk PA 16802 USA

An algorithm is presented for finding a maximum independent set in a connected graph with n vertices and m edges in time O(poly (n) 1.2365(m-n)). As a consequence, we find a maximum independent set in a graph of degre... 详细信息

ISBN: (纸本)354032755X

关键词： maximum independent set exponential time algorithm sparse graph NP-hard

来源：评论

学校读者我要写书评

暂无评论

Cost-based solution for optimizing multi-join queries over distributed streaming sensor data

Cost-based solution for optimizing multi-join queries over d...

引用

International Conference on Collaborative Computing

作者： Gomes, Joseph Choi, Hyeong-Ah George Washington Univ Dept Comp Sci Washington DC 20052 USA

ISBN: (纸本)9781424404285

Sensors are envisioned to be at the center of distributed collaborative computing services involving time-critical decision support. Sensors are small devices with limited communication and computational capabilities that collect data on their neighboring physical world and send the data periodically to server machines. Sensors form a collaborative network with these servers, where the sensors gather information and the servers perform various operations (e.g. filter, aggregate, join etc) on the information streams in real-time according to predefined queries or rules. Sensor data streams are continuous, un-ending and have highly volatile characteristics. As a result, traditional database systems are inappropriate for handling queries for sensor streams, and several stream data management systems have been proposed in the literature. In this paper we focus on a special type of query, namely join queries, which is the most expensive query operator. Here, we address the problem of finding an optimal join tree that maximizes throughput for sliding window based multi-join queries over continuous sensor data streams. We present a polynomial time algorithm Fodp and three variants of Fodp. Our experiments in ARES(1). show that for almost all instances, trees from Fodp and its variants perform close to the optimal trees from our exponential time algorithm OptDP [1], and significantly better than existing XJoin based heuristic algorithms.

关键词： distributed sensors groupware query processing sensor fusion distributed streaming sensor data exponential time algorithm multijoin queries optimal join tree polynomial time algorithm sliding window

来源：评论

学校读者我要写书评

暂无评论

The supremum asymmetric norm on sequence algebras

引用

Electronic Notes in Theoretical Computer Science 2003年 74卷 39-50页

作者： L.M. García-Raffi S. Romaguera E.A. Sánchez-Pérez Escuela de Caminos Departamento de Matemática Aplicada Universidad Politécnica de Valencia 46071 Valencia Spain

Recently, E.A. Emerson and C.S. Jutla (SIAM J. Comput., 1999), have successfully applied complexity of tree automata to obtain optimal deterministic exponential time algorithms for some important modal logics of programs. The running time of these algorithms corresponds, of course, to complexity functions which are potential functions and, thus, they do not belong, in general, to any dual p -complexity space. Motivated by these facts we here introduce and study a very general class of complexity spaces, which provides, in the dual context, a suitable framework to carry out a description of the complexity functions that generate exponential time algorithms. In particular, such spaces can be modelled as biBanach semialgebras which are isometrically isomorphic to the positive cone of the asymmetric normed linear space consisting of bounded sequences of real numbers endowed with the supremum asymmetric norm.

关键词： asymmetric norms semialgebra biBanach exponential time algorithm sup P(n) -complexity space isometrically isomorphic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：