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

Efficient recognition of equimatchable graphs

INFORMATION PROCESSING LETTERS 2014年第1-2期114卷 66-71页

作者： Demange, Marc Ekim, Tinaz ESSEC Business Sch Paris France LAMSADE UMR 7243 Paris France Bogazici Univ Dept Ind Engn Istanbul Turkey

In this paper, we give a new characterization of equimatchable graphs that are graphs with all maximal matchings having the same size. This gives an O(n(2)m)-algorithm for deciding whether a general graph of order n and with m edges is equimatchable. An O(n(4.5)) recognition algorithm based on the Gallai-Edmonds Decomposition already follows from Lesk et al. (1984) [8]. Our characterization and algorithm use only some basic knowledge on matchings and can be formulated in a simplier way. Moreover it leads to a better time complexity. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Maximal matching Edge dominating set Equimatchable

来源：评论

学校读者我要写书评

暂无评论

Using Covert Topological Information for Defense Against Malicious Attacks on DC State Estimation

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2014年第7期32卷 1471-1485页

作者： Bi, Suzhi Zhang, Ying Jun Natl Univ Singapore Fac Engn Dept Elect & Comp Engn Singapore 119077 Singapore Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China Chinese Univ Hong Kong Shenzhen Res Inst Shenzhen Peoples R China

Accurate state estimation is of paramount importance to maintain the power system operating in a secure and efficient state. The recently identified coordinated data injection attacks to meter measurements can bypass the current security system and introduce errors to the state estimates. The conventional wisdom to mitigate such attacks is by securing meter measurements to evade malicious injections. In this paper, we provide a novel alternative to defend against false data injection attacks using covert power network topological information. By keeping the exact reactance of a set of transmission lines from attackers, no false data injection attack can be launched to compromise any set of state variables. We first investigate from the attackers' perspective the necessary condition to perform an injection attack. Based on the arguments, we characterize the optimal protection problem, which protects the state variables with minimum cost, as a well-studied Steiner tree problem in a graph. In addition, we also propose a mixed defending strategy that jointly considers the use of covert topological information and secure meter measurements when either method alone is costly or unable to achieve the protection objective. A mixed-integer linear programming formulation is introduced to obtain the optimal mixed defending strategy. To tackle the NP-hardness of the problem, a tree-pruning-based heuristic is further presented to produce an approximate solution in polynomial time. The advantageous performance of the proposed defending mechanisms is verified in IEEE standard power system test cases.

关键词： False-data injection attack power system state estimation smart grid security graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

graphical Methods for Defense Against False-Data Injection Attacks on Power System State Estimation

引用

IEEE TRANSACTIONS ON SMART GRID 2014年第3期5卷 1216-1227页

作者： Bi, Suzhi Zhang, Ying Jun (Angela) Natl Univ Singapore Dept Elect & Comp Engn Singapore 119077 Singapore Chinese Univ Hong Kong Dept Informat Engn Shatin Hong Kong Peoples R China

The normal operation of power system relies on accurate state estimation that faithfully reflects the physical aspects of the electrical power grids. However, recent research shows that carefully synthesized false-data injection attacks can bypass the security system and introduce arbitrary errors to state estimates. In this paper, we use graphical methods to study defending mechanisms against false-data injection attacks on power system state estimation. By securing carefully selected meter measurements, no false data injection attack can be launched to compromise any set of state variables. We characterize the optimal protection problem, which protects the state variables with minimum number of measurements, as a variant Steiner tree problem in a graph. Based on the graphical characterization, we propose both exact and reduced-complexity approximation algorithms. In particular, we show that the proposed tree-pruning based approximation algorithm significantly reduces computational complexity, while yielding negligible performance degradation compared with the optimal algorithms. The advantageous performance of the proposed defending mechanisms is verified in IEEE standard power system testcases.

关键词： False-data injection attack graph algorithms power system state estimation smart grid security

来源：评论

学校读者我要写书评

暂无评论

Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree

引用

ALGORITHMICA 2014年第2期68卷 337-357页

作者： Bilo, Davide Guala, Luciano Proietti, Guido Univ Aquila Dipartimento Informat I-67010 Laquila Italy Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy CNR Ist Anal Sistemi & Informat I-00185 Rome Italy

Given an n-node, undirected and 2-edge-connected graph G=(V,E) with positive real weights on its m edges, given a set of k source nodes SaS dagger V, and given a spanning tree T of G, the routing cost from S of T is the sum of the distances in T from every source saS to all the other nodes of G. If an edge e of T undergoes a transient failure, and one needs to promptly reestablish the connectivity, then to reduce set-up and rerouting costs it makes sense to temporarily replace e by means of a swap edge, i.e., an edge in G reconnecting the two subtrees of T induced by the removal of e. Then, a best swap edge for e is a swap edge which minimizes the routing cost from S of the tree obtained after the swapping. As a natural extension, the all-best swap edges problem is that of finding a best swap edge for every edge of T, and this has been recently solved in O(mn) time and linear space. In this paper, we focus our attention on the relevant cases in which k=O(1) and k=n, which model realistic communication paradigms. For these cases, we improve the above result by presenting an time and linear space algorithm. Moreover, for the case k=n, we also provide an accurate analysis showing that the obtained swap tree is effective in terms of routing cost. Indeed, if the input tree T has a routing cost from V which is a constant-factor away from that of a minimum routing-cost spanning tree (whose computation is a problem known to be in APX), and if in addition nodes in T enjoys a suitable distance stretching property from a tree centroid (which can be constructively induced, as we show), then the tree obtained after the swapping has a routing cost from V which is still a constant-ratio approximation of that of a new (i.e., in the graph deprived of the failed edge) minimum routing-cost spanning tree.

关键词： graph algorithms Minimum routing-cost spanning tree Transient edge failures All-best swap edges problems

来源：评论

学校读者我要写书评

暂无评论

Stateless generation of distributed virtual worlds

引用

COMPUTERS & graphICS-UK 2014年第0期44卷 33-44页

作者： Danihelka, Jiri Kencl, Lukas Zara, Jiri Czech Tech Univ Fac Elect Engn Prague Czech Republic

We present novel techniques for implementing possibly infinite on-demand generated 3D virtual worlds in distributed environments. Our approach can be useful in two scenarios: 1. A multiuser virtual world with mobile clients with sufficient CPU and GPU power but with limited network speed. This reflects current mobile phones, tablets and laptops in areas without a high-speed mobile connection or Wi-Fi connectivity. 2. Virtual world on-demand generation in a cloud environment that would be useful for scalable massive multiplayer games. If multiple independent generators create areas that are over-lapping, our method ensures that the intersection of the areas will contain the same geometry for all of them. For this reason, we call our method stateless generation. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： graph algorithms Path problems Distributed graphics Computational geometry Urban modeling

来源：评论

学校读者我要写书评

暂无评论

Surfing the Network for Ranking by Multidamping

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第9期26卷 2323-2336页

作者： Kollias, Giorgos Gallopoulos, Efstratios Grama, Ananth Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Purdue Univ Ctr Sci Informat W Lafayette IN 47907 USA Univ Patras Comp Engn & Informat Dept GR-26500 Patras Greece

PageRank is one of the most commonly used techniques for ranking nodes in a network. It is a special case of a family of link-based rankings, commonly referred to as functional rankings. Functional rankings are computed as power series of a stochastic matrix derived from the adjacency matrix of the graph. This general formulation of functional rankings enables their use in diverse applications, ranging from traditional search applications to identification of spam and outliers in networks. This paper presents a novel algorithmic (re) formulation of commonly used functional rankings, such as LinearRank, TotalRank and Generalized Hyperbolic Rank. These rankings can be approximated by finite series representations. We prove that polynomials of stochastic matrices can be expressed as products of Google matrices (matrices having the form used in Google's original PageRank formulation). Individual matrices in these products are parameterized by different damping factors. For this reason, we refer to our formulation as multidamping. We demonstrate that multidamping has a number of desirable characteristics: (i) for problems such as finding the highest ranked pages, multidamping admits extremely fast approximate solutions;(ii) multidamping provides an intuitive interpretation of existing functional rankings in terms of the surfing habits of model web users;(iii) multidamping provides a natural framework based on Monte Carlo type methods that have efficient parallel and distributed implementations. It also provides the basis for constructing new link-based rankings based on inhomogeneous products of Google matrices. We present algorithms for computing damping factors for existing functional rankings analytically and numerically. We validate various benefits of multidamping on a number of real datasets.

关键词： Ranking graph algorithms Markov processes Mining methods and algorithms Personalization Web mining Monte Carlo

来源：评论

学校读者我要写书评

暂无评论

On atomic structure of P₅-free subclasses and Maximum Weight Independent Set problem

引用

THEORETICAL COMPUTER SCIENCE 2014年 516卷 78-85页

作者： Karthick, T. Indian Stat Inst Chennai Ctr Comp Sci Unit Madras 600113 Tamil Nadu India

graph decompositions play a crucial role in structural graph theory and in designing efficient graph algorithms. Among them, clique separator decomposition (a decomposition tree of the graph whose leaves have no clique separator (so-called atoms)) used by Tarjan for solving various optimization problems recently received much attention. In this note, we first derive the atomic structure of two subclasses of P-5-free graphs, where P-5 is a chordless path on five vertices. These results enable us to provide efficient solutions for the MAXIMUM WEIGHT INDEPENDENT SET problem in these classes of graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithms Clique separators Modular decomposition Maximum Weight Independent Set problem P-5-free graphs

来源：评论

学校读者我要写书评

暂无评论

Join-Reachability Problems in Directed graphs

引用

THEORY OF COMPUTING SYSTEMS 2014年第2期55卷 347-379页

作者： Georgiadis, Loukas Nikolopoulos, Stavros D. Palios, Leonidas Univ Ioannina Dept Comp Sci GR-45110 Ioannina Greece

For a given collection of directed graphs we define the join-reachability graph of , denoted by , as the directed graph that, for any pair of vertices u and v, contains a path from u to v if and only if such a path exists in all graphs of . Our goal is to compute an efficient representation of . In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for . In the implicit version we wish to build an efficient data structure, in terms of space and query time, such that we can report fast the set of vertices that reach a query vertex in all graphs of . This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problems. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.

关键词： algorithms Data structures graph algorithms Reachability Combinatorial complexity

来源：评论

学校读者我要写书评

暂无评论

WEB PAGE PREDICTION ENHANCED WITH CONFIDENCE MECHANISM

引用

JOURNAL OF WEB ENGINEERING 2014年第5-6期13卷 507-524页

作者： Gellert, Arpad Florea, Adrian Lucian Blaga Univ Sibiu Dept Comp Sci & Elect Engn Sibiu Romania

In this work we comparatively present and evaluate different prediction techniques used to anticipate and prefetch web pages and files accessed via browsers. The goal is to reduce the delays necessary to load the web pages and files visited by the users. We have included into our analysis Markov chains, Hidden Markov Models and graph algorithms. We have enhanced all these predictors with confidence mechanism which classifies dynamically web pages as predictable or unpredictable. A prediction is generated only if the confidence counter attached to the current web page is in a predictable state, improving thus the accuracy. Based on the results we have also developed a hybrid predictor consisting in a Hidden Markov Model and a graph-based predictor. The experiments show that this hybrid predictor provides the best prediction accuracies, an average of 85.45% on the "Ocean Group Research" dataset from the University of Boston and 87.28% on the dataset collected from the educational web server of our university, being thus the most appropriate to efficiently predict and prefetch web pages.

关键词： Web page prediction prefetching Markov chains Hidden Markov Models graph algorithms browser extension

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：