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

algorithms for Balanced graph Colorings with Applications in Parallel Computing

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第5期28卷 1240-1256页

作者： Lu, Hao Halappanavar, Mahantesh Chavarria-Miranda, Daniel Gebremedhin, Assefaw H. Panyala, Ajay Kalyanaraman, Ananth Washington State Univ Pullman WA 99164 USA Pacific Northwest Natl Lab Richland WA 99354 USA

graph coloring-in a generic sense-is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.

关键词： Balanced coloring parallel graph coloring distance-1 coloring partial distance-2 coloring Tilera manycore architecture community detection graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Independent Set Reconfiguration in H-Free graphs 50th

Independent Set Reconfiguration in H-Free Graphs

引用

50th International Workshop on graph-Theoretic Concepts in Computer Science

作者： Bartier, Valentin Bousquet, Nicolas Muhlenthaler, Moritz Univ Lyon 1 Univ Lyon CNRS LIRIS UMRCNRS 5205 F-69621 Lyon France Univ Grenoble Alpes G SCOP St Martin Dheres France

ISBN: (纸本)9783031754081;9783031754098

Given a graph G and two independent sets of G, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of G. We study the complexity of this problem for H-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev's theorem for connected graphs H, showing that the problem is PSPACE-complete unless H is a path or a subdivision of the claw. We then show that under the token sliding rule the problem admits a polynomial-time algorithm if the input graph is fork-free, generalizing known results for P4-free graphs and claw-free graphs. This implies a complete classification of the complexity of token sliding in H-free graphs, H being connected or not.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Constant-Round Domination on graphs of High Girth and Low Expansion 26th

Tight Bounds for Constant-Round Domination on Graphs of High...

引用

26th International Symposium on Stabilization, Safety, and Security of Distributed Systems

作者： Lenzen, Christoph Wenning, Sophie CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

ISBN: (纸本)9783031744976;9783031744983

A long-standing open question is which graph class is the most general one permitting constant-time constant-factor approximations for dominating sets. The approximation ratio has been bounded by increasingly general parameters such as genus, arboricity, or expansion of the input graph. Amiri and Wiederhake considered k-hop domination in graphs of bounded k-hop expansion and girth at least 4k+ 3 [2];the k-hop expansion f(k) of a graph family denotes the maximum ratio of edges to nodes that can be achieved by contracting disjoint subgraphs of radius k and deleting nodes. In this setting, these authors to obtain a simple O(k)-round algorithm achieving approximation ratio Theta(kf(k)). In this work, we study the same setting but derive tight bounds: - A Theta(kf(k))-approximation is possible in k, but not k - 1 rounds. - In 3k rounds an O(k + f(k)(k/(k+1)))-approximation can be achieved. - No constantround deterministic algorithm can achieve approximation ratio o(k + f(k)(k/(k+1))). Our upper bounds hold in the port numbering model with small messages, while the lower bounds apply to local algorithms, i.e., with arbitrary message size and unique identifiers. This means that the constant-time approximation ratio can be sublinear in the edge density of the graph, in a graph class which does not allow a constant approximation. This begs the question whether this is an artefact of the restriction to high girth or can be extended to all graphs of k-hop expansion f(k).

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graph operations on parity games and polynomial-time algorithms

引用

THEORETICAL COMPUTER SCIENCE 2016年 614卷 97-108页

作者： Dittmann, Christoph Kreutzer, Stephan Tomescu, Alexandru I. Tech Univ Berlin Chair Log & Semant Berlin Germany Univ Helsinki Dept Comp Sci Helsinki Inst Informat Technol HIIT FIN-00014 Helsinki Finland

In this paper we establish polynomial-time algorithms for special classes of parity games. In particular we study various constructions for combining graphs that often arise in structural graph theory and show that polynomial-time solvability of parity games is preserved under these operations. This includes the join of two graphs, repeated pasting along vertices, and the addition of a vertex. As a consequence we obtain polynomial time algorithms for parity games whose underlying graph is an orientation of a complete graph (such as tournaments), a complete bipartite graph, a block graph, or a block-cactus graph. These are "classes where the problem was not known to be efficiently solvable before. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Parity games graph theory Directed graphs Tournaments graph operations graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks 25

A Sublinear Algorithm for Approximate Shortest Paths in Larg...

引用

18th ACM International Conference on Web Search and Data Mining, WSDM 2025

作者： Basu, Sabyasachi Kōshima, Nadia Eden, Talya Ben-Eliezer, Omri Seshadhri, C. UC Santa Cruz Santa CruzCA United States Massachusetts Institute of Technology CambridgeMA United States Bar-Ilan University Ramat Gan Israel Technion - Israel Institute of Technology Haifa Israel Amazon CupertinoCA United States

ISBN: (纸本)9798400713293

Computing distances and finding shortest paths in massive real-world networks is a fundamental algorithmic task in network analysis. There are two main approaches to solving this task. On one end are traversal-based algorithms like bidirectional breadth-first search (BiBFS), which have no preprocessing step but are slow on individual distance inquiries. On the other end are indexing-based approaches, which create and maintain a large index. This allows for answering individual inquiries very fast;however, index creation is prohibitively expensive. We seek to bridge these two extremes: quickly answer distance inquiries without the need for costly preprocessing. We propose a new algorithm and data structure, WormHole, for approximate shortest path computations. WormHole leverages structural properties of social networks to build a sublinearly sized index, drawing upon the core-periphery decomposition of Ben-Eliezer et al [10]. Empirically, WormHole's preprocessing time improves upon index-based solutions by orders of magnitude: indexing billion edges graphs takes only a few minutes. Real time performance is consistently much faster than in BiBFS. The acceleration comes at the cost of a minor accuracy trade-off. We complement these empirical results with provable theoretical guarantees. © 2025 Copyright held by the owner/author(s).

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Depth-Width Tradeoffs in Algorithmic Reasoning of graph Tasks with Transformers

arXiv

引用

arXiv 2025年

作者： Yehudai, Gilad Sanford, Clayton Bechler-Speicher, Maya Fischer, Orr Gilad-Bachrach, Ran Globerson, Amir Courant Institute of Mathematical Sciences New York University United States Google Research United States Blavatnik School of Computer Science Tel-Aviv University Meta United States Bar-Ilan University Computer Science Department Department of Bio-Medical Engineering Tel-Aviv University Edmond J. Safra Center for Bioinformatics Tel-Aviv University

Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorithmic tasks a key question is what is the minimal size of a transformer that can implement a task. Recent work has begun to explore this problem for graph-based tasks, showing that for sub-linear embedding dimension (i.e., model width) logarithmic depth suffices. However, an open question, which we address here, is what happens if width is allowed to grow linearly. Here we analyze this setting, and provide the surprising result that with linear width, constant depth suffices for solving a host of graph-based problems. This suggests that a moderate increase in width can allow much shallower models, which are advantageous in terms of inference time. For other problems, we show that quadratic width is required. Our results demonstrate the complex and intriguing landscape of transformer implementations of graph-based algorithms. We support our theoretical results with empirical evaluations. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets

引用

Egyptian Informatics Journal 2025年 30卷

作者： Yakut, Selman Software Engineering Department Faculty of Engineering Inonu University Malatya44000 Turkey

The graph Coloring Problem (GCP) is an NP-hard problem that aims to color the vertices of a graph using the minimum number of distinct colors, ensuring that adjacent vertices do not share the same color. GCP is widely applied in real-world scenarios and graph theory problems. Despite numerous studies on solving GCP, existing methods face limitations, often performing well on specific graph types but failing to deliver efficient solutions across diverse structures. This study introduces the Malatya Sequent Independent Set Coloring Algorithm as an effective solution for GCP. The algorithm utilizes the Malatya Centrality Algorithm to compute Malatya Centrality (MC) values for graph vertices, where an MC value is defined as the sum of the ratios of a vertex's degree to its neighbors’ degrees. The algorithm selects the vertex with the lowest MC value, adds it to an independent set, and removes it along with its neighbors and edges. This process repeats until the first sequent independent set is identified. The removed set is then excluded from the original graph, and the process continues on the remaining structure to determine additional sequent independent sets, ensuring that each set corresponds to a single color group in GCP. The algorithm was tested on social network graphs, random graphs, and benchmark datasets, supported by mathematical analyses and proofs. The results confirm that the algorithm provides efficient, polynomial-time solutions for GCP and maintains high performance across various graph types, independent of constraints. © 2025

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graph PROPERTY UPDATE algorithms AND THEIR APPLICATION TO DISTANCE MATRICES

引用

INFOR 1982年第2-3期20卷 178-201页

作者： CHESTON, GA CORNEIL, DG Dept. of Computational Science Univ. of Saskatchewan Saskatoon Sask. Canada S7N 0W0 Dept. of Computer Science Univ. of Toronto Toronto Ontario Canada M5S 1A7

algorithms are considered to update graph properties after small changes have been made to a graph. Such update algorithms can use the approach either of directly determining the properties from the new graph or of actually updating the properties of the previous graph. Unfortunately, the execution times for the update algorithms developed by these two approaches often have the same worst-case order. One approach to comparing algorithms with equal worst-case orders is to count the frequency of execuuon for key operations, called active operations. For a class of algorithms that includes most update algorithms this technique can be extended to couniiiig the frequency of execution for active blocks of code. The approaches to the development of update algorithms and the use of active blocksin comparisons will be illustrated by the problem of updating ihe distance matrix of an undirected graph after an edge or vertex has been added or deleted.RésuméGet article considére les algorithmes mise à jour les propriétés d’un graphe aprés faisant les petites changements. Ces tels algorithmes mise à jour peuveni utiliser la méthode de déterminant directement les proprietes du graphe nouveau, ou en misant à jour véritablement les proprietés du graphe antérieur. Malheureusement, le temps exécuté pour les algorithmes mise à jour ont développé par ces deux méthodes qui ont souvent le même ordre de grandeur. Une méthode pour comparant les algorithmes avec les ordres égals de grandeur est de compter la fréquence d’exécution pour ies opérations principales, appelé opérations actifs. Pour une classe d’algorithmes qui comprend la plupart des algorilhmes mise à jour, cette méthode peut être généralisé à compter te fréquence d’exécution pour blocs actifs de code. Les méthodes pour le développement des algorithmes mise à jour et emploi des blocs actifs dans comparaisons seront illustrés par le probiéme de misant à jour la matrice d’distance d’un graphe non-orienté aprés une arête ou un somme

关键词： Analysis of algorithms Breadth-first search Computational complexity Distance matrix graph algorithms Update

来源：评论

学校读者我要写书评

暂无评论

Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

引用

INFORMATION PROCESSING LETTERS 2004年第4期89卷 165-173页

作者： Brandstädt, A Le, VB De Ridder, HN Univ Rostock Fachbereich Informat D-18051 Rostock Germany

Modular decomposition of graphs is a powerful tool for designing efficient algorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time algorithms for MWS on chair- and xbull-free graphs which considerably extend an earlier result on bull- and chair-free graphs by De Simone and Sassano (the chair is the graph with vertices a, b, c, d, e and edges ab, be, cd, be, and the xbull is the graph with vertices a, b, c, d, e, f and edges ab, be, cd, de, bf, cf). Moreover, our algorithm is robust in the sense that we do not have to check in advance whether the input graphs are indeed chair- and xbull-free. (C) 2003 Elsevier B.V. All rights reserved.

关键词： efficient graph algorithms robust graph algorithms modular decomposition maximum weight stable set problem on graphs graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for dominating induced matching based on graph partition

引用

DISCRETE APPLIED MATHEMATICS 2015年 190卷 147-162页

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

A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges in the graph such that no two edges in F share a common endpoint and each edge in E \ F is incident with exactly one edge in F. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.1467(n)n(0(1)) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F, where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph), After giving several structural properties of the problem, we show that the problem always contains some "good vertices," branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Exact algorithms graph algorithms graph partition Branch-and-reduce Dominating induced matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：