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

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Williams, Ryan Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781450328869

First-order logic captures a vast number of computational problems on graphs. We study the time complexity of deciding graph properties definable by first-order sentences in prenex normal form with k variables. The trivial algorithm for this problem runs in O(n(k)) time on n-node graphs (the big-O hides the dependence on k). Answering a question of Miklos Ajtai, we give the first algorithms running faster than the trivial algorithm, in the general case of arbitrary first-order sentences and arbitrary graphs. One algorithm runs in O(n(k-3+omega)) <= O(n(k-0.627)) time for all k >= 3, where omega < 2.373 is the n x n matrix multiplication exponent. By applying fast rectangular matrix multiplication, the algorithm can be improved further to run in n(k-1+o(1)) time, for all k >= 9. Finally, we observe that the exponent of k - 1 is optimal, under the popular hypothesis that CNF satisfiability with n variables and m clauses cannot be solved in (2 - epsilon)(n) . poly(m) time for some epsilon > 0.

关键词： first-order logic graph algorithms matrix multiplication satisfiability

来源：评论

学校读者我要写书评

暂无评论

Global t-Sweep Coverage Problem with Minimum Interference

Global t-Sweep Coverage Problem with Minimum Interference

引用

International Conference on Information Technology

作者： B. K. Bhatta S. K. Jena Computer Science and Application Group Department of Mathematics Indian Institute of Technology Delhi School of Math.-Stat-Computer Science Utkal University

ISBN: (纸本)9781509004881

Sweep coverage is one of the important and recent issue for network monitoring in wireless sensor network (WSN). Sweep coverage is efficiently applicable where periodic monitoring is sufficient than continuous monitoring. Interference minimization is another main objective of topology control problem in wireless sensor network. Reducing interference in turn reduces the number of collision and packet retransmission, which decreases the energy consumption and increases lifetime of the network. In this paper, we introduce the Interference minimization global t-Gsweep coverage problem (IMGtSCP) where the objective is to minimize the interference number induced by set of mobile and static sensors with the constraint that the given set of point of interests (PoIs) guarantee t-Gsweep coverage. We prove that the IMGtSCP problem is NP-hard and cannot be approximated with a factor 2. We propose a new heuristic called Interference Minimization Sweep Coverage with Static and Mobile Sensors. We have shown that the time complexity of this heuristics is O(n~3 log n), We also conduct simulation to show the performance of our proposed algorithm.

关键词： Wireless Sensor Networks Topology Control Minimum Spanning Tree graph algorithms Sweep Coverage K-MST Mobile Sensors Interference

来源：评论

学校读者我要写书评

暂无评论

CITEX: A new citation index to measure the relative importance of authors and papers in scientific publications

CITEX: A new citation index to measure the relative importan...

引用

IEEE International Conference on Communications

作者： Arindam Pal Sushmita Ruj TCS Innovation Labs Indian Statistical Institute

ISBN: (纸本)9781467364300

Evaluating the performance of researchers and measuring the impact of papers written by scientists is the main objective of citation analysis. Various indices and metrics have been proposed for this. In this paper, we propose a new citation index CITEX, which gives normalized scores to authors and papers to determine their rankings. To the best of our knowledge, this is the first citation index which simultaneously assigns scores to both authors and papers. Using these scores, we can get an objective measure of the reputation of an author and the impact of a paper. We model this problem as an iterative computation on a publication graph, whose vertices are authors and papers, and whose edges indicate which author has written which paper. We prove that this iterative computation converges in the limit, by using a powerful theorem from linear algebra. We run this algorithm on several examples, and find that the author and paper scores match closely with what is suggested by our intuition. The algorithm is theoretically sound and runs very fast in practice. We compare this index with several existing metrics and find that CITEX gives far more accurate scores compared to the traditional metrics.

关键词： CITATION ANALYSIS graph algorithms MATRIX COMPUTATIONS EIGENVALUES AND EIGENVECTORS INFORMATION RETRIEVAL

来源：评论

学校读者我要写书评

暂无评论

Measuring the Sensitivity of graph Metrics to Missing Data

Measuring the Sensitivity of Graph Metrics to Missing Data

引用

10th International Conference on Parallel Processing and Applied Mathematics (PPAM)

作者： Zakrzewska, Anita Bader, David A. Georgia Inst Technol Atlanta GA 30332 USA

ISBN: (纸本)9783642552243

The increasing energy consumption of high performance computing has resulted in rising operational and environmental costs. Therefore, reducing the energy consumption of computation is an emerging area of interest. We study the approach of data sampling to reduce the energy costs of sparse graph algorithms. The resulting error levels for several graph metrics are measured to analyze the trade-off between energy consumption reduction and error. The three types of graphs studied, real graphs, synthetic random graphs, and synthetic small-world graphs, each show distinct behavior. Across all graphs, the error cost is initially relatively low. For example, four of the five real graphs studied needed less than a third of total energy to retain a degree centrality rank correlation coefficient of 0.85 when random vertices were removed. However, the error incurred for further energy reduction grows at an increasing rate, providing diminishing returns.

关键词： graphs graph algorithms Sensitivity analysis Missing data Energy consumption Power

来源：评论

学校读者我要写书评

暂无评论

Efficient and Dynamic algorithms for Alternating Buchi Games and Maximal End-Component Decomposition

引用

JOURNAL OF THE ACM 2014年第3期61卷 1–40页

作者： Chatterjee, Krishnendu Henzinger, Monika IST Austria A-3400 Klosterneuburg Austria Univ Vienna Res Grp Theory & Applicat Algorithms A-1090 Vienna Austria

The computation of the winning set for Buchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is (O) over tilde (n. m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the 0(n m) boundary by presenting a new technique that reduces the running time to 0(n(2)). This bound also leads to O(n(2))-time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of 0(n,. m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n(3))), and (3) in Markov decision processes (improving for m > n(4/3) an earlier bound of O(m.,root m)). We then show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in 0(n) amortized time per operation. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(*** m)-time algorithm, and our second algorithm is an 0(n2)-time algorithm which is obtained using the same technique as for alternating Buchi games. Thus, we obtain an O(min{m . root m, n(2)})-time algorithm improving the long-standing O(n . m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem.

关键词： algorithms Verification graph games Buchi objectives graph algorithms dynamic graph algorithms verification and synthesis

来源：评论

学校读者我要写书评

暂无评论

TWO-STAGE ROBUST OPTIMIZATION, STATE-SPACE REPRESENTABLE UNCERTAINTY AND APPLICATIONS

引用

RAIRO-OPERATIONS RESEARCH 2014年第4期48卷 455-475页

作者： Minoux, Michel Univ Paris 06 LIP6 F-75252 Paris 05 France

The present paper addresses the class of two-stage robust optimization problems which can be formulated as mathematical programs with uncertainty on the right-hand side coefficients (RHS uncertainty). The wide variety of applications and the fact that many problems in the class have been shown to be NP-hard, motivates the search for efficiently solvable special cases. Accordingly, the first objective of the paper is to provide an overview of the most important applications and of various polynomial or pseudo-polynomial special cases identified so far. The second objective is to introduce a new subclass of polynomially solvable robust optimization problems with RHS uncertainty based on the concept of state-space representable uncertainty sets. A typical application to a multi period energy production problem under uncertain customer load requirements is described into details, and computational results including a comparison between optimal two-stage solutions and exact optimal multistage strategies are discussed.

关键词： Robust optimization graph algorithms Min-Max optimization

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Threat Propagation for Network Security

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2014年第9期9卷 1394-1405页

作者： Carter, Kevin M. Idika, Nwokedi Streilein, William W. MIT Lincoln Lab Lexington MA 02420 USA

Techniques for network security analysis have historically focused on the actions of the network hosts. Outside of forensic analysis, little has been done to detect or predict malicious or infected nodes strictly based on their association with other known malicious nodes. This methodology is highly prevalent in the graph analytics world, however, and is referred to as community detection. In this paper, we present a method for detecting malicious and infected nodes on both monitored networks and the external Internet. We leverage prior community detection and graphical modeling work by propagating threat probabilities across network nodes, given an initial set of known malicious nodes. We enhance prior work by employing constraints that remove the adverse effect of cyclic propagation that is a byproduct of current methods. We demonstrate the effectiveness of probabilistic threat propagation on the tasks of detecting botnets and malicious web destinations.

关键词： Network security botnet blacklist graph algorithms community detection

来源：评论

学校读者我要写书评

暂无评论

Hardness and approximation of minimum maximal matchings

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2014年第8期91卷 1635-1654页

作者： Demange, Marc Ekim, Tinaz Tanasescu, Cerasela ESSEC Business Sch F-95021 Cergy Pontoise France CNRS UMR 7243 LAMSADE Paris France Bogazici Univ Dept Ind Engn TR-34342 Bebek Turkey

In this paper, we consider the minimum maximal matching problem in some classes of graphs such as regular graphs. We show that the minimum maximal matching problem is NP-hard even in regular bipartite graphs, and a polynomial time exact algorithm is given for almost complete regular bipartite graphs. From the approximation point of view, it is well known that any maximal matching guarantees the approximation ratio of 2 but surprisingly very few improvements have been obtained. In this paper we give improved approximation ratios for several classes of graphs. For example any algorithm is shown to guarantee an approximation ratio of (2-o(1)) in graphs with high average degree. We also propose an algorithm guaranteeing for any graph of maximum degree Delta an approximation ratio of (2 -1/Delta), which slightly improves the best known results. In addition, we analyse a natural linear-time greedy algorithm guaranteeing a ratio of (2 -23/18k) in k-regular graphs admitting a perfect matching.

关键词： graph algorithms minimum maximal matching edge dominating set regular graphs NP-completeness and approximation

来源：评论

学校读者我要写书评

暂无评论

Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期547卷 1-17页

作者： Dragan, Feodor F. Abu-Ata, Muad Kent State Univ Dept Comp Sci Algorithm Res Lab Kent OH 44242 USA

In this paper, we study collective additive tree spanners for families of graphs enjoying special Robertson-Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. We say that a graph G admits a system of mu collective additive tree r-spanners (resp., multiplicative tree t-spanners) if there is a system T(G) of at most mu spanning trees of G such that for any two vertices x, y of G a spanning tree T is an element of T(G) exists such that d(T) (x, y) <= d(G) (x, y) + r (resp., d(T) (x, y) <= t . d(G) (x, y)). When mu=1 one gets the notion of additive tree r-spanner (resp., multiplicative tree t-spanner). It is known that if a graph G has a multiplicative tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most [t/2] in G. We use this to demonstrate that there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner, constructs a system of at most log(2)n collective additive tree O (t logn)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can "turn" a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result by showing that if a graph G admits a multiplicative t-spanner with tree-width k-1, then G admits a Robertson-Seymour's tree-decomposition each bag of which can be covered with at most k disks of G of radius at most [t/2] each. This is used to demonstrate that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k-1, constructs a system of at most k(1 + log(2)n) collective additive tree O (t logn)-spanners of G. (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithms Approximation algorithms Tree spanner problem Collective tree spanners Spanners of bounded tree-width Robertson-Seymour's tree-decomposition Balanced separators

来源：评论

学校读者我要写书评

暂无评论

PEBBLING IN SPLIT graphS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2014年第3期28卷 1449-1466页

作者： Alcon, Liliana Gutierrez, Marisa Hurlbert, Glenn Univ Nacl La Plata Fac Ciencias Exactas Dept Matemat RA-1900 La Plata Buenos Aires Argentina Arizona State Univ Sch Math & Stat Tempe AZ 85287 USA

graph pebbling is a network optimization model for transporting discrete resources that are consumed in transit: the movement of 2 pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding whether a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter 2 graphs, and that deciding whether the pebbling number has a prescribed upper bound is Pi(P)(2)-complete. On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers;for example, complete graphs, products of paths (including cubes), trees, cycles, diameter 2 graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guarantee it, with no characterization in sight. In this paper we investigate an important family of diameter 3 chordal graphs called split graphs;graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in O(n(beta)) time, where beta = 2 omega/(omega+1) congruent to 1.41 and omega congruent to 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.

关键词： pebbling number split graphs class 0 graph algorithms complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：