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

arXiv 2025年

作者： Ulyanov, Nikolay

The Berge–Fulkerson conjecture states that every bridgeless cubic graph can be covered with six perfect matchings such that each edge is covered exactly twice. An equivalent reformulation is that it’s possible to find a 6-cycle 4-cover. In this paper we discuss the oriented version (o6c4c) of the latter statement, pose it as a conjecture and prove it for the family of Isaacs flower snarks. Similarly to the case of oriented cycle double cover, we can always construct an orientable surface (possibly with boundary) from an o6c4c solution. If the o6c4c solution itself splits into two (not necessarily oriented) cycle double covers, then it’s also possible to build another pair of orientable surfaces (also possibly with boundaries). Finally we show how to build a ribbon graph, and for some special o6c4c cases we show that this ribbon graph corresponds to an oriented 6-cycle double cover. © 2025, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Longer Attention Span: Increasing Transformer Context Length with Sparse graph Processing Techniques

arXiv

引用

arXiv 2025年

作者： Tomczak, Nathaniel Kuppannagari, Sanmukh Computer and Data Sciences Case Western Reserve University ClevelandOH United States

—Transformers have demonstrated great success in numerous domains including natural language processing and bioinformatics. This success stems from the use of the attention mechanism by these models in order to represent and propagate pairwise interactions between individual tokens of sequential data. However, the primary limitation of this operation is its quadratic memory and time complexity in relation to the input’s context length – the length of a sequence over which the interactions need to be captured. This significantly limits the length of sequences that can be inferred upon by these models. Extensive research has been conducted to reduce the number of pairwise interactions to sub-quadratic in relation to the context length by introducing sparsity into the attention mechanism through the development of sparse attention masks. However, efficient implementations that achieve "true sparsity" are lacking. In this work, we address this issue by proposing a graph computing view of attention where tokens are perceived as nodes of the graph and the attention mask determines the edges of the graph. Using this view, we develop graph processing algorithms to implement the attention mechanism. Both theoretically and empirically, we demonstrate that our algorithms only perform the needed computations, i.e., they are work optimal. We also perform extensive experimentation using popular attention masks to explore the impact of sparsity on execution time and achievable context length. Our experiments demonstrate significant speedups in execution times compared to state-of-the-art attention implementations such as FlashAttention for large sequence lengths. We also demonstrate that our algorithms are able to achieve extremely long sequence lengths of as high as 160 million on a single NVIDIA A100 GPU (SXM4 80GB). Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Matrix Completion with graph Information: A Provable Nonconvex Optimization Approach

arXiv

引用

arXiv 2025年

作者： Wang, Yao Yang, Yiyang Wang, Kaidong Gao, Shanxing Liao, Xiuwu School of Management Xi’an Jiaotong University Xi’an China

We consider the problem of matrix completion with graphs as side information depicting the interrelations between variables. The key challenge lies in leveraging the graph’s similarity structure to enhance matrix recovery. Existing approaches, primarily based on graph Laplacian regularization, suffer from several limitations: (1) they focus only on the similarity between neighboring variables, while overlooking long-range correlations;(2) they are highly sensitive to false edges in the graphs and (3) they lack theoretical guarantees regarding statistical and computational complexities. To address these issues, we propose in this paper a novel graph regularized matrix completion algorithm called GSGD, based on preconditioned projected gradient descent approach. We demonstrate that GSGD effectively captures the higher-order correlation information behind the graphs, and achieves superior robustness and stability against the false edges. Theoretically, we prove that GSGD achieves linear convergence to the global optimum with near-optimal sample complexity, providing the first theoretical guarantees for both recovery accuracy and efficacy in the perspective of nonconvex optimization. Our numerical experiments on both synthetic and real-world data further validate that GSGD achieves superior recovery accuracy and scalability compared with several popular alternatives. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

The MASEMPR Problem and Its Applications in Logistics 11th

The MASEMPR Problem and Its Applications in Logistics

引用

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

作者： Subramani, A. Subramani, K. Wojciechowski, Piotr Jena, Sangram K. Candorcare MorgantownWV United States LDCSEE West Virginia University MorgantownWV United States DCSSE Miami University OxfordOH United States

ISBN: (纸本)9783031834370

In this paper, we propose a new problem called the Maximum cardinality Acyclic Subset of Edges that Meets the Potential Requirements (MASEMPR). This problem abstracts several problems in logistics. Our focus is on a particular logistics problem called the Maximum Path Set (MPS) problem. We show that the MASEMPR problem is NP-hard. We then propose an exact exponential algorithm for the MASEMPR problem in subcubic graphs (graphs in which each vertex has degree at most 3). Finally, we design a constant factor approximation algorithm for the MASEMPR problem in general graphs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Reachability in Temporal graphs Under Perturbation 50th

Reachability in Temporal Graphs Under Perturbation

引用

50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025

作者： Enright, Jessica Larios-Jones, Laura Meeks, Kitty Pettersson, William School of Computing Science University of Glasgow Glasgow United Kingdom

ISBN: (纸本)9783031826696

Reachability and other path-based measures on temporal graphs can be used to understand spread of infection, information, and people in modelled systems. Due to delays and errors in reporting, temporal graphs derived from data are unlikely to perfectly reflect reality, especially with respect to the precise times at which edges appear. To reflect this uncertainty, we consider a model in which some number ζ of edge appearances may have their labels perturbed by ±δ for some δ. Within this model, we investigate temporal reachability and consider the problem of determining the maximum number of vertices any vertex can reach under these perturbations. We show this problem to be intractable in general but efficiently solvable when ζ is sufficiently large. We also give algorithms which solve this problem in several restricted settings. We complement this with some contrasting results concerning the complexity of related temporal eccentricity problems under perturbation. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Branching Random Walks and Their Applications 28

Distributed Branching Random Walks and Their Applications

引用

28th International Conference on Principles of Distributed Systems, OPODIS 2024

作者： Aradhya, Vijeth Gilbert, Seth Götte, Thorsten National University of Singapore Singapore University of Hamburg Germany

ISBN: (纸本)9783959773607

In recent years, the explosion of big data and analytics has necessitated distributed storage and processing with several compute nodes (e.g., multiple datacenters). These nodes collaboratively perform parallel computation, where the data is typically partitioned across these nodes to ensure scalability, redundancy and load-balancing. But the nodes may not always be co-located;in many cases, they are part of a larger communication network. Since those nodes only need to communicate among themselves, a key challenge is to design efficient routes catered to that subnetwork. In this work, we initiate the study of distributed sampling and routing problems for subnetworks in any well-connected network. Given any network G = (V,E) with mixing time τmix, consider the canonical problem of permutation routing [Ghaffari, Kuhn and Su, PODC 2017] that aims to minimize both congestion and dilation of the routes, where the demands (i.e., set of source-terminal pairs) are such that each node sends or receives number of messages proportional to its degree. We show that the permutation routing problem, when demands are restricted to any subset S ⊆ V (i.e., subnetwork), can be solved in exp(O(√log |S|)) · Õ(τmix) rounds (where Õ (·) hides polylogarithmic factors of |V |). This means that the running time depends subpolynomially on the subnetwork size (i.e., not on the entire network size). The ability to solve permutation routing efficiently immediately implies that a large class of parallel algorithms can be simulated efficiently on the subnetwork. As a prerequisite to constructing efficient routes, we design and analyze distributed branching random walks that distribute tokens started by the nodes in the subnetwork. At a high-level, these algorithms operate by always moving each token according to a (lazy) simple random walk, but also branching a token into multiple tokens at some specified intervals;ultimately, if a node starts a branching walk, with its id in a token, then by the

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Neighborhood Exploration for Dynamic Independent Sets∗

Optimal Neighborhood Exploration for Dynamic Independent Set...

引用

2025 SIAM Symposium on Algorithm Engineering and Experiments, ALENEX 2025

作者： Borowitz, Jannick Großmann, Ernestine Schulz, Christian Heidelberg University Germany

ISBN: (纸本)9798331311995

A dynamic graph algorithm is a data structure that supports edge insertions, deletions, and problem specific queries. While extensive research exists on dynamic algorithms for graph problems solvable in polynomial time, most of these algorithms have not been implemented or empirically evaluated. This work addresses the NP-complete maximum weight as well as the maximum cardinality independent set problem in a dynamic setting, applicable to areas like dynamic map-labeling and vehicle routing. In this work, specifically we introduce a novel local search technique called optimal neighborhood exploration. This technique creates independent subproblems that are solved to optimality, leading to improved overall solutions. Through numerous experiments, we assess the effectiveness of our approach and compare it with other state-of-the-art dynamic solvers. Our algorithm features a parameter, the subproblem size, that balances running time and solution quality. Copyright © 2025 by SIAM.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating Densest Subgraph in Geometric Intersection graphs 42

Approximating Densest Subgraph in Geometric Intersection Gra...

引用

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

作者： Har-Peled, Sariel Rahul, Saladi Department of Computer Science University of Illinois at Urbana-Champaign IL United States Bangalore India

ISBN: (纸本)9783959773652

For an undirected graph G = (V, E), with n vertices and m edges, the densest subgraph problem, is to compute a subset S ⊆ V which maximizes the ratio |ES|/|S|, where ES ⊆ E is the set of all edges of G with endpoints in S. The densest subgraph problem is a well studied problem in computer science. Existing exact and approximation algorithms for computing the densest subgraph require Ω(m) time. We present near-linear time (in n) approximation algorithms for the densest subgraph problem on implicit geometric intersection graphs, where the vertices are explicitly given but not the edges. As a concrete example, we consider n disks in the plane with arbitrary radii and present two different approximation algorithms. As a by-product, we show a reduction from (shallow) range-reporting to approximate counting/sampling which seems to be new and is useful for other problems such as independent query sampling. © Sariel Har-Peled and Saladi Rahul.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple Sublinear algorithms for (∆ + 1) Vertex Coloring via Asymmetric Palette Sparsification 8

Simple Sublinear Algorithms for (∆ + 1) Vertex Coloring via...

引用

8th SIAM Symposium on Simplicity of algorithms, SOSA 2025

作者： Assadi, Sepehr Yazdanyar, Helia Cheriton School of Computer Science University of Waterloo Canada

ISBN: (纸本)9781611978315

The palette sparsification theorem (PST) of Assadi, Chen, and Khanna (SODA 2019) states that in every graph G with maximum degree ∆, sampling a list of O(log n) colors from {1, ..., ∆ + 1} for every vertex independently and uniformly, with high probability, allows for finding a (∆ + 1) vertex coloring of G by coloring each vertex only from its sampled list. PST naturally leads to a host of sublinear algorithms for (∆ + 1) vertex coloring, including in semi-streaming, sublinear time, and MPC models, which are all proven to be nearly optimal, and in the case of the former two are the only known sublinear algorithms for this problem. While being a quite natural and simple-to-state theorem, PST suffers from two drawbacks. Firstly, all its known proofs require technical arguments that rely on sophisticated graph decompositions and probabilistic arguments. Secondly, finding the coloring of the graph from the sampled lists in an efficient manner requires a considerably complicated algorithm. We show that a natural weakening of PST addresses both these drawbacks while still leading to sublinear algorithms of similar quality (up to polylog factors). In particular, we prove an asymmetric palette sparsification theorem (APST) that allows for list sizes of the vertices to have different sizes and only bounds the average size of these lists. The benefit of this weaker requirement is that we can now easily show the graph can be (∆ + 1) colored from the sampled lists using the standard greedy coloring algorithm. This way, we can recover nearly-optimal bounds for (∆ + 1) vertex coloring in all the aforementioned models using algorithms that are much simpler to implement and analyze. Copyright © 2025 by SIAM.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

NOBGP: A Novel Optimized Balanced graph Partitioning Algorithm 19th

NOBGP: A Novel Optimized Balanced Graph Partitioning Algorit...

引用

19th CCF Conference on Computer Supported Cooperative Work and Social Computing, ChineseCSCW 2024

作者： Chen, Jiebin Hu, Ziqiang Ye, Renjie Zhang, Qishan Guo, Kun College of Computer and Data Science Fuzhou University Fuzhou350108 China Engineering Research Center of Big Data Intelligence Ministry of Education Fuzhou350108 China Fujian Key Laboratory of Network Computing and Intelligent Information Processing Fuzhou University Fuzhou350108 China Xianda College of Economics and Humanities Shanghai International Studies University Shanghai China

ISBN: (纸本)9789819623723

Large-scale graphs have become prevalent with the advent of the big data era. Distributed graph computing systems are commonly used for processing and analyzing large-scale graphs, with graph partitioning being a key prerequisite for their efficient computation. graph partitioning aims to balance the load across partitions while minimizing the number of cut-edges. Moreover, it should achieve high efficiency and scalability. However, the existing popular graph partitioning algorithms do not fully take into account the internal topology of real-world graphs, which affects the final partition quality and convergence. Meanwhile, they easily fall into the local optimum due to partition load constraints. This paper introduces a Novel Optimized Balanced graph Partitioning algorithm (NOBGP). First, we propose an initialization strategy based on label propagation of core vertices to achieve initial partitions with good locality and accelerate convergence. Second, we optimize the label propagation process to ensure balanced partitions and propose a probability-based disruption strategy to avoid the local optimum. We implement NOBGP on the distributed graph computing framework graphX. Extensive experimental results on real-world graphs show that the proposed algorithm is scalable and performs better than the existing algorithms. We also run PageRank and Louvain applications using the graph partitioning results to demonstrate the efficiency of our algorithm. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：