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

32nd Annual European Symposium on algorithms, ESA 2024

作者： de Carvalho Pereira, Felipe de Rezende, Pedro Jussieu Yunes, Tallys Morato, Luiz Fernando Batista Institute of Computing University of Campinas Brazil Miami Herbert Business School University of Miami Coral GablesFL United States

ISBN: (纸本)9783959773386

We propose an exact algorithm for the graph Burning Problem (GBP), an NP-hard optimization problem that models the spread of influence on social networks. Given a graph G with vertex set V, the objective is to find a sequence of k vertices in V, namely, v1, v2, ..., vk, such that k is minimum and Ski=1{u ∈ V : d(u, vi) ≤ k − i} = V, where d(u, v) denotes the distance between u and v. We formulate the problem as a set covering integer programming model and design a row generation algorithm for the GBP. Our method exploits the fact that a very small number of covering constraints is often sufficient for solving the integer model, allowing the corresponding rows to be generated on demand. To date, the most efficient exact algorithm for the GBP, denoted here by GDCA, is able to obtain optimal solutions for graphs with up to 14,000 vertices within two hours of execution. In comparison, our algorithm finds provably optimal solutions approximately 236 times faster, on average, than GDCA. For larger graphs, memory space becomes a limiting factor for GDCA. Our algorithm, however, solves real-world instances with more than 3 million vertices in less than 19 minutes, increasing the size of graphs for which optimal solutions are known by a factor of 200. Additionally, we conduct tests on the proposed algorithm using a series of challenging instances composed of grid graphs containing up to 5,000 vertices. As a result, we achieve novel optimal solutions and tight optimality gaps that have not been previously reported in the literature. © Felipe de Carvalho Pereira, Pedro Jussieu de Rezende, Tallys Yunes, and Luiz Fernando Batista Morato;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Prime, Composite and Fundamental Kirchhoff graphs 1

引用

53rd Southeastern International Conference on Combinatorics, graph Theory, and Computing, SEICCGTC 2022

作者： Wang, Jessica Fehribach, Joseph D. Worcester Polytechnic Institute WorcesterMA United States

ISBN: (数字)9783031621666

ISBN: (纸本)9783031621659

A Kirchhoff graph is a vector graph with orthogonal cycles and vertex cuts. An algorithm has been developed that constructs all the Kirchhoff graphs up to a fixed edge multiplicity. This algorithm is used to explore the structure of prime Kirchhoff graph tilings. The existence of infinitely many prime Kirchhoff graphs for a given set of fundamental Kirchhoff graphs is established, as is the existence of a minimal multiplicity for Kirchhoff graphs to exist. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Parameterized Algorithm for Vertex and Edge Connectivity of Embedded graphs 32

A Parameterized Algorithm for Vertex and Edge Connectivity o...

引用

32nd Annual European Symposium on algorithms, ESA 2024

作者： Biedl, Therese Bose, Prosenjit Murali, Karthik University of Waterloo Canada School of Computer Science Carleton University Ottawa Canada

ISBN: (纸本)9783959773386

The problem of computing vertex and edge connectivity of a graph are classical problems in algorithmic graph theory. The focus of this paper is on computing these parameters for graphs drawn on the plane. A typical example of such graphs are planar graphs which can be embedded without any crossings. It has long been known that vertex and edge connectivity of planar embedded graphs can be computed in linear time. Very recently, Biedl and Murali extended the techniques from planar graphs to 1-plane graphs without ×-crossings, i.e., crossings whose endpoints induce a matching. While the tools used were novel, they were highly tailored to 1-plane graphs, and do not provide much leeway for further extension. In this paper, we develop alternate techniques that are simpler, have wider applications to near-planar graphs, and can be used to test both vertex and edge connectivity. Our technique works for all those embedded graphs where any pair of crossing edges are connected by a path that, roughly speaking, can be covered with few cells of the drawing. Important examples of such graphs include optimal 2-planar and optimal 3-planar graphs, d-map graphs, d-framed graphs, graphs with bounded crossing number, and k-plane graphs with bounded number of ×-crossings. © Therese Biedl, Prosenjit Bose, and Karthik Murali;licensed under Creative Commons License CC-BY 4.0.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

VGL: a high-performance graph processing framework for the NEC SX-Aurora TSUBASA vector architecture

引用

JOURNAL OF SUPERCOMPUTING 2021年第8期77卷 8694-8715页

作者： Afanasyev, Ilya V. Voevodin, Vladimir V. Komatsu, Kazuhiko Kobayashi, Hiroaki Moscow Ctr Fundamental & Appl Math Moscow 119991 Russia Moscow MV Lomonosov State Univ Res Comp Ctr Moscow 119234 Russia Tohoku Univ Sendai Miyagi 9808579 Japan

Developing efficient graph algorithms implementations is an extremely important problem of modern computer science, since graphs are frequently used in various real-world applications. graph algorithms typically belong to the data-intensive class, and thus using architectures with high-bandwidth memory potentially allows to solve many graph problems significantly faster compared to modern multicore CPUs. Among other supercomputer architectures, vector systems, such as the SX family of NEC vector supercomputers, are equipped with high-bandwidth memory. However, the highly irregular structure of many real-world graphs makes it extremely challenging to implement graph algorithms on vector systems, since these implementations are usually bulky and complicated, and a deep understanding of vector architectures hardware features is required. This paper presents the world first attempt to develop an efficient and simultaneously simple graph processing framework for modern vector systems. Our vector graph library (VGL) framework targets NEC SX-Aurora TSUBASA as a primary vector architecture and provides relatively simple computational and data abstractions. These abstractions incorporate many vector-oriented optimization strategies into a high-level programming model, allowing quick implementation of new graph algorithms with a small amount of code and minimal knowledge about features of vector systems. In this paper, we evaluate the VGL performance on four widely used graph processing problems: breadth-first search, single source shortest paths, connected components, and page rank. The provided comparative performance analysis demonstrates that the VGL-based implementations achieve significant acceleration over the existing high-performance frameworks and libraries: up to 14 times speedup over multicore CPUs (Ligra, Galois, GAPBS) and up to 3 times speedup compared to NVIDIA GPU (Gunrock, NVgraph) implementations.

关键词： NEC SX-Aurora TSUBASA graph algorithms graph frameworks VGL Vector processing High-performance computing

来源：评论

学校读者我要写书评

暂无评论

Efficient Distance Sensitivity oracles for Real-World graph Data

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第1期33卷 85-99页

作者： Lee, Jong-Ryul Chung, Chin-Wan Korea Adv Inst Sci & Technol Daejeon 34141 South Korea Chongqing Univ Technol CQUT Chongqing Liangjiang KAIST Int Program Chongqing 400054 Peoples R China Korea Adv Inst Sci & Technol KAIST Sch Comp Daejeon 34141 South Korea

A distance sensitivity oracle is a data structure answering queries that ask the shortest distance from a node to another in a network expecting node/edge failures. It has been mainly studied in theory literature, but all the existing oracles for a directed graph suffer from prohibitive preprocessing time and space. Motivated by this, we develop two practical distance sensitivity oracles for directed graphs as variants of Transit Node Routing. The first oracle consists of a novel fault-tolerant index structure, which is used to construct a solution path and to detect and localize the impact of network failures, and an efficient query algorithm for it. The second oracle is made by applying the A* heuristics to the first oracle, which exploits lower bound distances to effectively reduce search space. In addition, we propose additional speed-up techniques to make our oracles faster with a slight loss of accuracy. We conduct extensive experiments with real-life datasets, which demonstrate that our oracles greatly outperform all of competitors in most cases. To the best of our knowledge, our oracles are the first distance sensitivity oracles that handle real-world graph data with million-level nodes.

关键词： graph algorithms path and circuit problems graphs and networks distance sensitivity oracle distance query shortest distance shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in graphs and Message-Passing algorithms

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2022年第2期16卷 234-249页

作者： Yu, Pei-Duo Tan, Chee Wei Fu, Hung-Lin Chung Yuan Christian Univ Dept Appl Math Taoyuan 320314 Taiwan Nanyang Technol Univ Singapore 639798 Singapore Natl Yang Ming Chiao Tung Univ Hsinchu 300093 Taiwan

We study the epidemic source detection problem in contact tracing networks modeled as a graph-constrained maximum likelihood estimation problem using the susceptible-infected model in epidemiology. Based on a snapshot observation of the infection subgraph, we first study finite degree regular graphs and regular graphs with cycles separately, thereby establishing a mathematical equivalence in maximal likelihood ratio between the case of finite acyclic graphs and that of cyclic graphs. In particular, we show that the optimal solution of the maximum likelihood estimator can be refined to distances on graphs based on a novel statistical distance centrality that captures the optimality of the nonconvex problem. An efficient contact tracing algorithm is then proposed to solve the general case of finite degree-regular graphs with multiple cycles. Our performance evaluation on a variety of graphs shows that our algorithms outperform the existing state-of-the-art heuristics using contact tracing data from the SARS-CoV 2003 and COVID-19 pandemics by correctly identifying the superspreaders on some of the largest superspreading infection clusters in Singapore and Taiwan.

关键词： COVID-19 Signal processing algorithms Public healthcare Pandemics Maximum likelihood estimation Probabilistic logic Coronaviruses Maximum likelihood estimation computational epidemiology contact tracing COVID-19 graph algorithms inference algorithms probability

来源：评论

学校读者我要写书评

暂无评论

Euclidean graphs as Crack Pattern Descriptors for Automated Crack Analysis in Digital Images

引用

SENSORS 2022年第16期22卷 5942页

作者： Strini, Alberto Schiavi, Luca Consiglio Nazl Ric ITC CNR Ist Tecnol Costruz Via Lombardia 49 I-20098 San Giuliano Milanese MI Italy

Typical crack detection processes in digital images produce a binary-segmented image that constitutes the basis for all of the following analyses. Binary images are, however, an unsatisfactory data format for advanced crack analysis algorithms due to their sparse nature and lack of significant data structuring. Therefore, this work instead proposes a new approach based on Euclidean graphs as functional crack pattern descriptors for all post-detection analyses. Conveying both geometrical and topological information in an integrated representation, Euclidean graphs are an ideal structure for efficient crack path description, as they precisely locate the cracks on the original image and capture salient crack skeleton features. Several Euclidean graph-based algorithms for autonomous crack refining, correlation and analysis are described, with significant advantages in both their capabilities and implementation convenience over the traditional, binary image-based approach. Moreover, Euclidean graphs allow the autonomous selection of specific cracks or crack parts based on objective criteria. Well-known performance metrics, namely precision, recall, intersection over union and F1-score, have been adapted for use with Euclidean graphs. The automated generation of Euclidean graphs from binary-segmented images is also reported, enabling the application of this technique to most existing detection methods (e.g., threshold-based or neural network-based) for cracks and other curvilinear features in digital images.

关键词： line-shaped feature description crack path descriptor image segmentation computer vision graph algorithms Dijkstra's algorithm performance evaluation indicators cracked cement surface structural damage assessment autonomous structure inspection

来源：评论

学校读者我要写书评

暂无评论

Hardness of Metric Dimension in graphs of Constant Treewidth

引用

ALGORITHMICA 2022年第11期84卷 3110-3155页

作者： Li, Shaohua Pilipczuk, Marcin Univ Warsaw Inst Informat Warsaw Poland

The METRIC DIMENSION problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S subset of V (G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of METRIC DIMENSION in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that METRIC DIMENSION is NP-hard in graphs of treewidth 24.

关键词： graph algorithms constant treewidth NP-hard

来源：评论

学校读者我要写书评

暂无评论

Twin-Width One 42

Twin-Width One

引用

42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025

作者： Ahn, Jungho Jacob, Hugo Köhler, Noleen Paul, Christophe Reinald, Amadeus Wiederrecht, Sebastian Seoul Korea Republic of LIRMM Université de Montpellier CNRS Montpellier France University of Leeds United Kingdom School of Computing KAIST Daejeon Korea Republic of

ISBN: (纸本)9783959773652

We investigate the structure of graphs of twin-width at most 1, and obtain the following results: graphs of twin-width at most 1 are permutation graphs. In particular they have an intersection model and a linear structure. There is always a 1-contraction sequence closely following a given permutation diagram. Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a 1-contraction sequence of a graph, or guarantees that it has twin-width more than 1. We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs. © Jungho Ahn, Hugo Jacob, Noleen Köhler, Christophe Paul, Amadeus Reinald, and Sebastian Wiederrecht.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

SDG_HHAG Framework: Homogeneous and Heterogeneous Attributed graphs 12th

SDG_HHAG Framework: Homogeneous and Heterogeneous Attribute...

引用

12th International Conference on Big Data and Artificial Intelligence, BDA 2024

作者： Sandhya Rani, A. Ashwitha, G. Swarupa Rani, K. University of Hyderabad Telangana Hyderabad India

ISBN: (纸本)9783031818202

graphs, comprising nodes, edges, and additional information known as attributed graphs, are essential for many applications which represents the complex data structures. Accessing these types of graphs is a significant challenge due to privacy concerns and the sensitivity of information. In addition, finding the attributed graphs with different node types and edge types is another challenge. Lack of attributed graph datasets with its heterogeneity factors hinders the powerful graph analysis algorithms across different fields. To address these challenges, we propose the SDG_HHAG Framework, a Synthetic Data Generation Framework comprising two approaches: 1) Synt_HoAG (Synthetic Homogeneous Attributed graphs) to enrich existing graphs with node and edge attributes, and 2) Synt_HeAG (Synthetic Heterogeneous Attributed graphs) to create and generate synthetic heterogeneous attributed graphs. We conducted experiments using the proposed approaches, and results reveal that these approaches are flexible to generate the synthetic graphs with attributes which are useful for graph analytics. Further, generated synthetic datasets are used for applications of social networks such as community detection and for the applications of routing problem such as query reachability. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：