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

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hua, Kevin Li, Daniel Park, Jaewoo Saranurak, Thatchaphol University of Michigan United States

We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected components (also known as shredders) and for finding the most shattering one, i.e., the one maximizing the number of connected components. Our algorithms break the quadratic time bound by Cheriyan and Thurimella (STOC’96) for both problems that has stood for more than two decades. Our work also removes a bottleneck to near-linear time algorithms for the vertex connectivity augmentation problem (Jordan’95). Note that it is necessary to list only minimum vertex cuts that separate the graph into at least three components because there can be an exponential number of minimum vertex cuts in general. To obtain near-linear time algorithms, we have extended techniques in local flow algorithms developed by Forster et al. (SODA’20) to list shredders on a local scale. We also exploit fast queries to a pairwise vertex connectivity oracle subject to vertex failures (Long and Saranurak FOCS’22, Kosinas ESA’23). This is the first application of connectivity oracles subject to vertex failures to speed up a static graph algorithm. © 2024, CC BY.

关键词： graph algorithms

graphFSA: A Finite State Automaton Framework for Algorithmic Learning on graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Grötschla, Florian Mathys, Joël Raun, Christoffer Wattenhofer, Roger ETH Zurich Switzerland

Many graph algorithms can be viewed as sets of rules that are iteratively applied, with the number of iterations dependent on the size and complexity of the input graph. Existing machine learning architectures often struggle to represent these algorithmic decisions as discrete state transitions. Therefore, we propose a novel framework: graphFSA (graph Finite State Automaton). graphFSA is designed to learn a finite state automaton that runs on each node of a given graph. We test graphFSA on cellular automata problems, showcasing its abilities in a straightforward algorithmic setting. For a comprehensive empirical evaluation of our framework, we create a diverse range of synthetic problems. As our main application, we then focus on learning more elaborate graph algorithms. Our findings suggest that graphFSA exhibits strong generalization and extrapolation abilities, presenting an alternative approach to represent these algorithms. © 2024, CC BY-NC-SA.

关键词： graph algorithms

The Largest and Smallest Eigenvalues of Matrices and Some Hamiltonian Properties of graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Rao Dept. of Computer Science Engineering and Mathematics University of South Carolina Aiken AikenSC29801 United States

Let G = (V,E) be a graph. We define matrices M(G;α,β)as αD + βA, where α, β are real numbers such that (α,β) ≠ (0,0) and D and A are the diagonal matrix and adjacency matrix of G, respectively. Using the largest and smallest eigenvalues of M(G;α,β) with α ≥ β > 0, we present sufficient conditions for the Hamiltonian and traceable graphs. © 2024, CC BY.

关键词： graph algorithms

Shortest Paths, Pigeonholes and Finite Sets : A Constructive Proof in Agda 24

学校读者我要写书评

暂无评论

Shortest Paths, Pigeonholes and Finite Sets : A Constructive...

Proceedings of the 36th Symposium on Implementation and Application of Functional Languages

作者： Michael Youssef University of Kaiserslautern-Landau (RPTU) Kaiserslautern Germany

BETTI NUMBERS OF NORMAL EDGE RINGS (II)

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Wang, Zexin Lu, Dancheng School of Mathematical Sciences Soochow University Suzhou215006 China

We compute the Betti numbers of the edge rings of multi-path graphs using the induced-subgraph method introduced in [19]. Here, a multi-path graph refers to a simple graph consisting of two vertices and multiple paths connecting them, which generalizes the complete bipartite graph K2,d. Special cases include the graph Gr,d introduced in [8], the graph Gr,s,d introduced in [12], and the graph B,h introduced in [10].MSC Codes 13A02, 05E40(Primary) 06D50(Secondary) © 2025, CC BY-NC-SA.

关键词： graph algorithms

Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Verma, Prashant Patna India

Degree Based Logical Adjacency Checking (DBLAC). An efficient coloring of graphs with unique logical AND operations. The logical AND operation shows More effective color assignment and fewer number of induced in the case of common edges between vertices. of colors used. In this work, we provide a detailed theoretical analysis of DBLAC's time and space complexity. It furthermore shows its effectiveness through prolonged experiments on standard benchmark graphs. We still compare with existing algorithms namely DSATUR, and Recursive Largest First (RLF). Second, we show how DBLAC achieves competitive results with respect to both the number of colors used and runtime. performance. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Hierarchical Multicriteria Shortest Path Search

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kurbanov, Temirlan Miao, Linxiao Vokřínek, Jiří The Department of Computer Science Faculty of Electrical Engineering Czech Technical University in Prague Czech Republic

This paper presents a novel multicriteria shortest path search algorithm called Hierarchical MLS. The distinguishing feature of the algorithm is the multilayered structure of compressed k-Path-Cover graphs it operates on. In addition to providing significant improvements in terms of time and memory consumption, the algorithm is notable for several other features. Due to the preprocessing phase requiring only several seconds, the algorithm can be successfully applied to scenarios with dynamic prices. Moreover, the algorithm does not employ bidirectional search, and can thus work on time-dependent metrics. We test the algorithm on multiple graphs and analyze its performance in terms of time and memory efficiency. The results prove Hierarchical MLS to be faster than its direct alternatives by at least 2 times in terms of query runtime and at least 20 times in terms of preprocessing. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

A Note on Mixed Cages of Girth 5

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Araujo-Pardo, Gabriela Mendoza-Cadena, Lydia Mirabel Instituto de Matemáticas Universidad Nacional Autónoma de México Campus Juriquilla Querétaro Mexico Center for Mathematical Modeling Universidad de Chile Santiago Chile

A mixed regular graph is a graph where every vertex has z incoming arcs, z outgoing arcs, and r edges;furthermore, if it has girth g, we say that the graph is a [z, r;g]-mixed graph. A [z, r;g]-mixed cage is a [z, r;g]-mixed graph with the smallest possible order. In this note, we give a family of [z, q;5]-mixed graphs for q ≥ 7 power of prime and q − 1 ≤ 4z + R with z ≥ 1 and R ∈ {1, . . ., 5}. This provides better upper bounds on the order of mixed cages until this moment. © 2025, CC BY.

关键词： graph algorithms

学校读者我要写书评

暂无评论

Twin-width one

arXiv 2025年

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

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. © 2025, CC BY.

关键词： graph algorithms