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

Using mincuts to design secret sharing schemes in graphs

引用

Electronic Notes in Discrete Mathematics 2003年 13卷 97-102页

作者： Poguntke, Werner Fachhochschule Südwestfalen 58095 Hagen Germany

来源：评论

学校读者我要写书评

暂无评论

Integrating Local & Global Features for Estimating Shortest-path Distance in Large-scale graphs

Integrating Local & Global Features for Estimating Shortest-...

引用

International Joint Conference on Neural Networks (IJCNN)

作者： Wang, Haoyu Yuan, Chun Pu, Yuan Tsinghua Univ Shenzhen Int Grad Sch Shenzhen Peoples R China Guangdong Baiyun Univ Guangzhou Peoples R China

ISBN: (纸本)9798350359329;9798350359312

We propose an effective hybrid approach jointly leveraging local and global features for shortest-path (SP) distance estimation in domain-agnostic large-scale graphs. Previous works struggle to make estimations either from node-wise local embeddings or by compressing a global SP distance matrix, causing insufficient learning at some distance and loss of accuracy. Unlike them, we find a way to better preserve local distance on node embeddings, and then integrate them with a global process for accurate estimation at every distance. First, we propose a distance-consistent embedding method that better preserves the distance between each node and its local neighbors due to resampling node occurrence on random walks. Second, we train a feed-forward network with boosting techniques (FFN-BT) to estimate SP distance from these embeddings plus existing global features. Experimental results show that our approach averagely yields 10% improved accuracy and 20% reduced time when compared to existing methods on a broad class of graphs.

关键词： Shortest path graph algorithm representation learning neural network model information retrieval

来源：评论

学校读者我要写书评

暂无评论

GreedyMAX-type algorithms for the Maximum Independent Set Problem

GreedyMAX-type Algorithms for the Maximum Independent Set Pr...

引用

37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

作者： Borowiecki, Piotr Goering, Frank Gdansk Univ Technol Dept Algorithms & Syst Modeling Fac Elect Telecommun & Informat Narutowicza 11-12 PL-80233 Gdansk Poland Fak Math D-09107 Chemnitz Germany

ISBN: (纸本)9783642183805

A maximum independent set problem for a simple graph G = (V, E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued function p defined on the vertex set V(G) and called a potential function of a graph G, while P(G) = max(upsilon is an element of v(G))p(upsilon) is called a potential of G. For any graph P(G) <= Delta(G), where Delta(G) is the maximum degree of G. Moreover, Delta(G) - Delta(G) may be arbitrarily large. A potential of a vertex lets us get a closer insight into the properties of its neighborhood which leads to the definition of the family of GreedyMAX-type algorithms having the classical GreedyMAX algorithm as their origin. We establish a lower bound 1/(P + 1) for the performance ratio of GreedyMAX-type algorithms which favorably compares with the bound 1/(Delta + 1) known to hold for GreedyMAX. The cardinality of an independent set generated by any GreedyMAX-type algorithm is at least Sigma(upsilon is an element of v(G))(p(upsilon) + 1)(-1), which strengthens the bounds of Turin and Caro-Wei stated in terms of vertex degrees.

关键词： independent set stable set graph algorithm greedy algorithm ordering potential of a graph

来源：评论

学校读者我要写书评

暂无评论

A Self-Stabilizing Protocol for Minimal Weighted Dominating Sets in Arbitrary Networks

A Self-Stabilizing Protocol for Minimal Weighted Dominating ...

引用

IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD)

作者： Wang, Guangyuan Wang, Hua Tao, Xiaohui Zhang, Ji Univ So Queensland Dept Maths & Comp Toowoomba Qld 4350 Australia

ISBN: (纸本)9781467360852;9781467360845

A lot of self-stabilizing algorithms for computing dominating sets problem have been proposed in the literature due to many real-life applications. Most of the proposed algorithms either work for dominating sets with a uniform weight or find approximation solutions to weighted dominating sets. However, for non-uniform weighted dominating sets (WDS) problem, there is no self-stabilizing algorithm for the WDS. Furthermore, how to find the minimal weighted dominating set is a challenge. In this paper, we propose a self-stabilizing algorithm for the minimal weighted dominating set (MWDS) under a central daemon model when operating in any general network. We further prove that the worst case convergence time of the algorithm from any arbitrary initial state is O(n(2)) steps where n is the number of nodes in the network.

关键词： Self-stabilizing algorithm Minimal weighted dominating set Central daemon graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration of Vertex-Disjoint Shortest Paths on graphs 17th

Reconfiguration of Vertex-Disjoint Shortest Paths on Graphs

引用

17th International Conference and Workshops on algorithms and Computation

作者： Saito, Rin Eto, Hiroshi Ito, Takehiro Uehara, Ryuhei Tohoku Univ Grad Sch Informat Sci Sendai Miyagi Japan Kyushu Inst Technol Sch Comp Sci & Syst Engn Iizuka Fukuoka Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Japan

ISBN: (纸本)9783031270505;9783031270512

We introduce and study reconfiguration problems for (internally) vertex-disjoint shortest paths: Given two tuples of internally vertex-disjoint shortest paths for fixed terminal pairs in an unweighted graph, we are asked to determine whether one tuple can be transformed into the other by exchanging a single vertex of one shortest path in the tuple at a time, so that all intermediate results remain tuples of internally vertex-disjoint shortest paths. We also study the shortest variant of the problem, that is, we wish to minimize the number of vertex-exchange steps required for such a transformation, if exists. These problems generalize the well-studied SHORTEST PATH RECONFIGURATION problem. In this paper, we analyze the complexity of these problems from the viewpoint of graph classes, and give some interesting contrast.

关键词： Combinatorial reconfiguration graph algorithm Vertex-disjoint paths

来源：评论

学校读者我要写书评

暂无评论

Balanced Centroidal Power Diagrams for Redistricting 18

Balanced Centroidal Power Diagrams for Redistricting

引用

26th ACM-SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS)

作者： Cohen-Addad, Vincent Klein, Philip N. Young, Neal E. Sorbonne Univ CNRS Paris France Brown Univ Providence RI 02912 USA Univ Calif Riverside Riverside CA 92521 USA

ISBN: (纸本)9781450358897

We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are "compact" and "contiguous," to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in R-3 such that the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a c

关键词： redistricting computational geometry optimization graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Integrating Cache Oblivious Approach with Modern Processor Architecture: The Case of Floyd-Warshall algorithm 2020

Integrating Cache Oblivious Approach with Modern Processor A...

引用

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)

作者： Endo, Toshio Tokyo Inst Technol GSIC RWBC OIL AIST Tokyo Japan

ISBN: (纸本)9781450372367

In order to implement algorithms on processors with deep cache hierarchy, the cache oblivious approach, which is based on recursive divide and conquer, is considered to be promising. This paper focuses on single-node implementation of Floyd-Warshall (FW) algorithm, which is an important graph computation kernel. For higher performance, another facility of modern processors, SIMD instructions need to be integrated to recursive approach efficiently. This paper describes a methodology to construct recursive implementations that takes architecture with SIMD and multi-core into account while harnessing cache. The experiment shows our FW implementation exhibits around 1.1 TFlops on a dual-socket SkyLake machine and 700 GFlops on a Xeon Phi machine, both of which have AVX512 SIMD ISA.

关键词： graph algorithm memory hierarchy cache oblivious SIMD

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs 24th

Characterizing Star-PCGs

引用

24th International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Sichuan Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

ISBN: (纸本)9783319947761;9783319947754

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d(min), d(max)) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d(min) <= d(max) such that G has an edge between two vertices u, v is an element of V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d(min), d(max)]. The tree T is also called a witness tree of the PCG G. The problem of testing if a given graph is a PCG is not known to be NP -hard yet. To obtain a complete characterization of PCGs is a wide open problem in computational biology and graph theory. In the literature, most witness trees admitted by known PCGs are stars and caterpillars. In this paper, we give a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph Polynomial-time algorithm graph algorithm graph theory

来源：评论

学校读者我要写书评

暂无评论

A Nearly-Linear Time algorithm for Minimizing Risk of Conflict in Social Networks 22

A Nearly-Linear Time Algorithm for Minimizing Risk of Confli...

引用

28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KKD)

作者： Zhu, Liwang Zhang, Zhongzhi Fudan Univ Shanghai Peoples R China Fudan Univ Shanghai Key Lab Intelligent Informat Proc Sch Comp Sci Shanghai 200433 Peoples R China

ISBN: (纸本)9781450393850

Concomitant with the tremendous prevalence of online social media platforms, the interactions among individuals are unprecedentedly enhanced. People are free to interact with acquaintances, express and exchange their own opinions through commenting, liking, retweeting on online social media, leading to resistance, controversy and other important phenomena over controversial social issues, which have been the subject of many recent works. In this paper, we study the problem of minimizing risk of conflict in social networks by modifying the initial opinions of a small number of nodes. We show that the objective function of the combinatorial optimization problem is monotone and supermodular. We then propose a naive greedy algorithm with a (1-1/e) approximation ratio that solves the problem in cubic time. To overcome the computation challenge for large networks, we further integrate several effective approximation strategies to provide a nearly linear time algorithm with a ( 1- 1/e - epsilon) approximation ratio for any error parameter epsilon > 0. Extensive experiments on various real-world datasets demonstrate both the efficiency and effectiveness of our algorithms. In particular, the fast one scales to large networks with more than two million nodes, and achieves up to 20x speed-up over the state-of-the-art algorithm.

关键词： Opinion dynamics graph algorithm resistance controversy social network discrete optimization

来源：评论

学校读者我要写书评

暂无评论

Query Optimal k-Plex Based Community in graphs (vol 2, pg 257, 2017)

引用

DATA SCIENCE AND ENGINEERING 2017年第4期2卷 274-274页

作者： Wang, Yue Jian, Xun Yang, Zhenhua Li, Jia Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China Huawei Technol Co Ltd Xian Peoples R China

In the initial publication, first name and family name of the second author Xun Jian were switched around. The original article has been corrected.

关键词： Community search graph algorithm K-plex

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：