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

Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2000年第2期36卷 205-240页

作者： Dahlhaus, E Univ Cologne Dept Math D-50969 Cologne Germany Univ Cologne Dept Comp Sci D-50969 Cologne Germany

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [7] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs, (C) 2000 Academic Press.

关键词： parallel algorithms graph algorithms split decomposition hierarchical clustering single linkage

来源：评论

学校读者我要写书评

暂无评论

Two Birds One Stone: Dual-Role Path Based Subgraph Matching Using Partial Evaluation 25th

Two Birds One Stone: Dual-Role Path Based Subgraph Matching ...

引用

25th International Conference on Web Information Systems Engineering, WISE 2024

作者： Li, Chengguo Wang, Xin Yin, Yongqi Wang, Hui College of Intelligence and Computing Tianjin University Tianjin China

ISBN: (纸本)9789819605668

In recent years, considerable attention has been drawn to the development of algorithms for subgraph matching in distributed scenarios. Many distributed engines inherently support join-based methods, which can lead to numerous redundant intermediate results and redundant processing. In contrast, exploration-based algorithms, though effective at limiting such extraneous results, necessitate arbitrary access to data. This paper introduces an efficient subgraph matching algorithm that leverages dual-role paths, which is implemented within the framework of partial evaluation and unifies the strengths of binary join and preprocessing enumeration approaches. During the partial evaluation phase, we decompose queries into dual-role paths to enhance the parallel capabilities of the system. For assembly, dual-role paths are treated as vertices for preprocessing enumeration, which reduces invalid intermediate results and avoids a large communication cost. The proposed algorithm has been implemented in a state-of-the-art distributed graph database system, and the comprehensive testing indicates that our proposed algorithm has increased efficiency by up to three times based on the partial evaluation framework. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

SBMGT: Scaling Bayesian Multinomial Group Testing 25

SBMGT: Scaling Bayesian Multinomial Group Testing

引用

30th Symposium on Principles and Practice of Parallel Programming

作者： Chen, Weicong Qi, Hao Tatsuoka, Curtis Lu, Xiaoyi Univ Calif Merced Merced CA 95343 USA Univ Pittsburgh Pittsburgh PA 15260 USA

ISBN: (纸本)9798400714436

Group testing is a widely used binary classification method that efficiently distinguishes between samples with and without a binary-classifiable attribute by pooling and testing subsets of a group. Bayesian Group Testing (BGT) is the state-of-the-art approach, which integrates prior risk information into a Bayesian Boolean Lattice framework to minimize test counts and reduce false classifications. However, BGT, like other existing group testing techniques, struggles with multinomial group testing, where samples have multiple binary-classifiable attributes that can be individually distinguished simultaneously. We address this need by proposing Bayesian Multinomial Group Testing (BMGT), which includes a new Bayesian-based model and supporting theorems for an efficient and precise multinomial pooling strategy. We further design and develop SBMGT, a high-performance and scalable framework to tackle BMGT's computational challenges by proposing three key innovations: 1) a parallel binaryencoded product lattice model with up to 99.8% efficiency;2) the Bayesian Balanced Partitioning Algorithm (BBPA), a multinomial pooling strategy optimized for parallel computation with up to 97.7% scaling efficiency on 4096 cores;and 3) a scalable multinomial group testing analytics framework, demonstrated in a real-world disease surveillance case study using AIDS and STDs datasets from Uganda, where SBMGT reduced tests by up to 54% and lowered false classification rates by 92% compared to BGT.

关键词： Multinomial group testing Bayesian methods Parallel algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficiency Unleashed: Reimagining A-to-B Paths in graphs 5th

Efficiency Unleashed: Reimagining A-to-B Paths in Graphs

引用

5th International Conference on Computing and Network Communications, CoCoNet 2023

作者： Sutejas, K. Ramalakshmi, K.S. Srinivas, K.S. Department of Computer Science and Engineering PES University Bengaluru India PES University Bengaluru India

ISBN: (纸本)9789819747108

Efficiently finding the shortest path in a graph is a fundamental problem with diverse applications across numerous domains, from transportation and network routing to social network analysis and bioinformatics. This paper presents a comprehensive approach to improving the efficiency of shortest path searches in generic graphs. The contributions encompass novel algorithmic enhancements and parallelization techniques to tackle this critical problem. These algorithmic enhancements optimize the traversal of graphs with diverse data types and leverage data encodings to enhance search speed, thus reducing computational overhead and making it feasible to handle large-scale graphs efficiently. To further expedite the shortest path search process, the parallelization technique harnesses the power of modern multi-core processors and distributed computing environments. By efficiently distributing the workload among multiple processing units, this strategy significantly accelerates the state-of-the-art algorithms like Dijkstra’s, to explore candidate paths, leading to substantial improvements in query response times. This approach has demonstrated superior performance characteristics in various scenarios and provides an additional layer of optimization. Evaluation of the parallelized approach on benchmark graph datasets has showcased its effectiveness by improving search efficiency and scalability over existing methods like Dijkstra’s Algorithm, A* Heuristic Search and the Bellman-Ford Algorithm. By integrating algorithmic enhancements and parallelization, the novel approach opens up new avenues for solving complex shortest path problems more efficiently with limited computational resources. This paper not only contributes to the field of graph algorithms but also provides a valuable toolkit for practitioners seeking to optimize shortest path searches in graph-based data structures. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Clique Partitioning-Based Algorithm for graph Compression

arXiv

引用

arXiv 2025年

作者： Chavan, Akshar Rabinia, Sanaz Grosu, Daniel Brocanelli, Marco The Ohio State University OH43210 United States Wayne State University MI48202 United States

Reducing the running time of graph algorithms is vital for tackling real-world problems such as shortest paths and matching in large-scale graphs, where path information plays a crucial role. This paper addresses this critical challenge of reducing the running time of graph algorithms by proposing a new graph compression algorithm that partitions the graph into bipartite cliques and uses the partition to obtain a compressed graph having a smaller number of edges while preserving the path information. This compressed graph can then be used as input to other graph algorithms for which path information is essential, leading to a significant reduction of their running time, especially for large, dense graphs. The running time of the proposed algorithm is O(mnδ), where 0 ≤ δ ≤ 1, which is better than O(mnδ log2 n), the running time of the best existing clique partitioning-based graph compression algorithm (the Feder-Motwani (FM) algorithm). Our extensive experimental analysis show that our algorithm achieves a compression ratio of up to 26% greater and executes up to 105.18 times faster than the FM algorithm. In addition, on large graphs with up to 1.05 billion edges, it achieves a compression ratio of up to 3.9, reducing the number of edges up to 74.36%. Finally, our tests with a matching algorithm on sufficiently large, dense graphs, demonstrate a reduction in the running time of up to 72.83% when the input is the compressed graph obtained by our algorithm, compared to the case where the input is the original uncompressed graph. © 2025, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

SpiderDAN: Matching Augmentation in Demand-Aware Networks

SpiderDAN: Matching Augmentation in Demand-Aware Networks

引用

2025 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2025

作者： Figiel, Aleksander Melnyk, Darya Nichterlein, André Pourdamghani, Arash Schmid, Stefan Technische Universität Berlin Germany

ISBN: (纸本)9798331311995

graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we consider a given physical network and the measured communication demands between the nodes. Our goal is to augment the given physical network with a matching, so that the shortest path lengths in the augmented network, weighted with the demands, are minimal. We prove that this problem is NP-hard, even if the physical network is a cycle. We then use results from demand-aware network design to provide a constant-factor approximation algorithm for adding a matching in case that only a few nodes in the network cause almost all the communication. For general real-world communication patterns, we design and evaluate a series of heuristics that can deal with arbitrary graphs as the underlying network structure. Our algorithms are validated experimentally using real-world traces (from e.g., Facebook) of data centers. Copyright © 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Sampling Unlabeled Chordal graphs in Expected Polynomial Time 42

Sampling Unlabeled Chordal Graphs in Expected Polynomial Tim...

引用

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

作者： Hébert-Johnson, Úrsula Lokshtanov, Daniel University of California Santa BarbaraCA United States

ISBN: (纸本)9783959773652

We design an algorithm that generates an n-vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1) an FPT algorithm for counting and sampling labeled chordal graphs with a given automorphism π, parameterized by the number of moved points of π, and (2) a proof that the probability that a random n-vertex labeled chordal graph has a given automorphism π ∈ Sn is at most 1/2c max{µ2,n}, where µ is the number of moved points of π and c is a constant. Our algorithm for sampling unlabeled chordal graphs calls the aforementioned FPT algorithm as a black box with potentially large values of the parameter µ, but the probability of calling this algorithm with a large value of µ is exponentially small. © Úrsula Hébert-Johnson and Daniel Lokshtanov.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Partial Domination in Some Geometric Intersection graphs 11th

Partial Domination in Some Geometric Intersection Graphs

引用

11th International Conference on algorithms and Discrete Applied Mathematics, CALDAM 2025

作者： Dutta, Madhura Maheshwari, Anil Nandy, Subhas C. TCG CREST Kolkata700091 India School of Computer Science Carleton University Ottawa Canada Ramkrishna Mission Vivekananda Centenary College Kolkata700118 India Ghaziabad201002 India

ISBN: (纸本)9783031834370

Partial domination problem is a generalization of the minimum dominating set problem on graphs. Here, instead of dominating all the nodes, one asks to dominate at least a fraction of the nodes of the given graph by choosing a subset of nodes of minimum size. For any real number α∈(0,1], α-partial domination problem can be proved to be NP-complete for general graphs. In this paper, we define the maximum dominating k-set of a graph which is polynomially transformable to the partial domination problem. We propose polynomial time algorithms for the maximum dominating k-set problem for some geometric intersection graphs, namely, interval graphs and unit square intersection graphs where the given squares are intersected by the straight line L:y=-x. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graphFuzz: Automated Testing of graph Algorithm Implementations with Differential Fuzzing and Lightweight Feedback

arXiv

引用

arXiv 2025年

作者： Yan, Wenqi Rigger, Manuel Wirth, Anthony Pham, Van-Thuan The University of Melbourne Australia National University of Singapore Singapore The University of Sydney Australia

graph algorithms, such as shortest path finding, play a crucial role in enabling essential applications and services like infrastructure planning and navigation, making their correctness important. However, thoroughly testing graph algorithm implementations poses several challenges, including their vast input space (i.e., arbitrary graphs). Moreover, through our preliminary study, we find that just a few automatically generated graphs (less than 10) could be enough to cover the code of many graph algorithm implementations, rendering the code coverage-guided fuzzing approach—one of the state-of-the-art search algorithms—less efficient than expected. To tackle these challenges, we introduce graphFuzz, the first automated feedback-guided fuzzing framework for graph algorithm implementations. Our key innovation lies in identifying lightweight and algorithm-specific feedback signals to combine with or completely replace the code coverage feedback to enhance the diversity of the test corpus, thereby speeding up the bug-finding process. This novel idea also allows graphFuzz to effectively work in both black-box (i.e., no code coverage instrumentation/collection is required) and grey-box setups. graphFuzz uses differential testing to detect logic bugs, in addition to crash-triggering bugs captured through exceptions. Our evaluation demonstrates the effectiveness of graphFuzz. The tool has successfully discovered 12 previously unknown bugs, including 6 logic bugs, in 9 graph algorithm implementations in two popular graph libraries, NetworkX and igraph. All of them have been confirmed and and 11 bugs have been rectified by the libraries’ maintainers. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Listing 6-Cycles in Sparse graphs 16

Listing 6-Cycles in Sparse Graphs

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Williams, Virginia Vassilevska Westover, Alek MIT CambridgeMA United States

ISBN: (纸本)9783959773614

This work considers the problem of output-sensitive listing of occurrences of 2k-cycles for fixed constant k ≥ 2 in an undirected host graph with m edges and t 2k-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an O(m4/3 + t) time algorithm for listing 4-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an Oe(n2 + t) time algorithm for listing 6-cycles in n node graphs. We focus on resolving the next natural question: obtaining listing algorithms for 6-cycles in the sparse setting, i.e., in terms of m rather than n. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou’s Oe(n2 + t) algorithm and Alon, Yuster and Zwick’s O(m5/3 + t) algorithm. We give an algorithm for listing 6-cycles with running time Oe(m1.6 + t). Our algorithm is a natural extension of Dahlgaard, Knudsen and Stöckel’s [STOC 2017] algorithm for detecting a 2k-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of "supersaturation" lemma relating the number of 2k-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and Stöckel’s 2k-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm. © Virginia Vassilevska Williams and Alek Westover.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：