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

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

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

A Space Improved Algorithm for Chromatic Number

学校读者我要写书评

暂无评论

SSRN

SSRN 2025年

作者： Wu, Pu Gu, Huanyu Jiang, Huiqin Shao, Zehui Xu, Jin School Of Computer Science Peking University Beijing100871 China Institute Of Computing Science And Technology Guangzhou University GuangDong Guangzhou510006 China Ministry Of Education Beijing100871 China

We investigate the chromatic number problem, a classic NP-complete problem identified by Karp among his 21 seminal problems. The chromatic number of a graph G is the smallest integer k such that each vertex of G can be assigned one of k colors, with no two adjacent vertices assigned the same color. The chromatic number problem requires determining this minimum k for a given graph G with n vertices. The questions of whether an algorithm for the chromatic number problem with time complexity O∗(an), where a ∗(2n) and polynomial space exists, both remain unresolved. The fastest known algorithm for the chromatic number problem was proposed by Björklund, Husfeldt, and Koivisto (FOCS 2006), with the time and space complexity of O∗(2n). Subsequently, in their follow-up work (ICALP 2010), the space complexity is reduced to O(1.2916n). In this work, we present an improved algorithm for the chromatic number problem. Building on prior research, our approach leverages algebraic methods, specifically the generating functions and the discrete Fourier transform. Our main contribution demonstrates that by utilizing these algebraic techniques, certain structural properties of graphs can be exploited to reduce space complexity, while preserving the best-known time complexity of O∗(2n). Specifically, our algorithm achieves a time complexity of O∗(2n) and a space complexity of O∗(Formlula presented) = O(1.2835n). © 2025, The Authors. All rights reserved.

关键词： graph algorithms

A SHORT PROOF OF GENERALIZED CONWAY–GORDON–SACHS THEOREM

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Nikkuni, Ryo Department of Information and Mathematical Sciences School of Arts and Sciences Tokyo Woman’s Christian University 2-6-1 Zempukuji Suginami-ku Tokyo167-8585 Japan

The famous Conway–Gordon–Sachs theorem for the complete graph on six vertices was extended to the general complete graph on n vertices by Kazakov–Korablev as a congruence modulo 2, and its integral lift was given by Morishita–Nikkuni. However, the proof is complicated and long. In this paper, we provide a shorter proof of the generalized Conway–Gordon–Sachs theorem over *** Codes 57M15, 57K10 © 2025, CC BY.

关键词： graph algorithms

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Li, Xiaoyu Liang, Yingyu Long, Jiangxuan Shi, Zhenmei Song, Zhao Zhuang, Zhen University of New South Wales Australia The University of Hong Kong Hong Kong University of Wisconsin-Madison United States South China University of Technology China The Simons Institute for the Theory of Computing The University of California Berkeley United States University of Minnesota United States

Looped Transformers have shown exceptional neural algorithmic reasoning capability in simulating traditional graph algorithms, but their application to more complex structures like hypergraphs remains underexplored. Hypergraphs generalize graphs by modeling higher-order relationships among multiple entities, enabling richer representations but introducing significant computational challenges. In this work, we extend the Loop Transformer architecture’s neural algorithmic reasoning capability to simulate hypergraph algorithms, addressing the gap between neural networks and combinatorial optimization over hypergraphs. Specifically, we propose a novel degradation mechanism for reducing hypergraphs to graph representations, enabling the simulation of graph-based algorithms, such as Dijkstra’s shortest path. Furthermore, we introduce a hyperedge-aware encoding scheme to simulate hypergraph-specific algorithms, exemplified by Helly’s algorithm. We establish theoretical guarantees for these simulations, demonstrating the feasibility of processing high-dimensional and combinatorial data using Loop Transformers. This work highlights the potential of Transformers as general-purpose algorithmic solvers for structured data. © 2025, CC BY.

关键词： graph algorithms

Interval H-graphs: Recognition and forbidden obstructions

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Müller, Haiko Rafiey, Arash School of Computer Science University of Leeds Leeds United Kingdom Indiana State University IN United States

We introduce the class of interval H-graphs, which is the generalization of interval graphs, particularly interval bigraphs. For a fixed graph H with vertices a1, a2, . . ., ak, we say that an input graph G with given partition V1, . . ., Vk of its vertices is an interval H-graph if each vertex v ∈ G can be represented by an interval Iv from a real line so that u ∈ Vi and v ∈ Vj are adjacent if and only if aiaj is an edge of H and intervals Iu and Iv intersect. G is called interval k-graph if H is a complete graph on k vertices. and interval bigraph when k = 2. We study the ordering characterization and forbidden obstructions of interval k-graphs and present a polynomial-time recognition algorithm for them. Additionally, we discuss how this algorithm can be extended to recognize general interval H-graphs. Special cases of interval k-graphs, particularly comparability interval k-graphs, were previously studied in [2], where the complexity interval k-graph recognition was posed as an open problem. © 2025, CC BY-NC-ND.

关键词： graph algorithms

Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Yu, Kaiqiang Wang, Kaixin Long, Cheng Lakshmanan, Laks Cheng, Reynold Nanyang Technological University Singapore Beijing University of Technology Beijing China The University of British Columbia Vancouver Canada The University of Hong Kong Hong Kong

Given two input graphs, finding the largest subgraph that occurs in both, i.e., finding the maximum common subgraph, is a fundamental operator for evaluating the similarity between two graphs in graph data analysis. Existing works for solving the problem are of either theoretical or practical interest, but not both. Specifically, the algorithms with a theoretical guarantee on the running time are known to be not practically efficient;algorithms following the recently proposed backtracking framework called McSplit, run fast in practice but do not have any theoretical guarantees. In this paper, we propose a new backtracking algorithm called RRSplit, which at once achieves better practical efficiency and provides a non-trivial theoretical guarantee on the worst-case running time. To achieve the former, we develop a series of reductions and upper bounds for reducing redundant computations, i.e., the time for exploring some unpromising branches of exploration that hold no maximum common subgraph. To achieve the latter, we formally prove that RRSplit incurs a worst-case time complexity which matches the best-known complexity for the problem. Finally, we conduct extensive experiments on several benchmark graph collections, and the results demonstrate that our algorithm outperforms the practical state-of-the-art by several orders of magnitude. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

On the characterization of graphs with tree 3-spanners

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Lin, Lan Lin, Yixun School of Electronics and Information Engineering Tongji University Shanghai200092 China School of Mathematics and Statistics Zhengzhou University Zhengzhou450001 China

The tree spanner problem for a graph G is as follows: For a given integer k, is there a spanning tree T of G (called a tree k-spanner) such that the distance in T between every pair of vertices is at most k times their distance in G? The minimum k that G admits a tree k-spanner is denoted by σ(G). It is well known in the literature that determining σ(G) ≤ 2 is polynomially solvable, while determining σ(G) ≤ k for k ≥ 4 is NP-complete. A long-standing open problem is to characterize graphs with σ(G) = 3. This paper settles this open problem by proving that it is polynomially *** Codes 05C35, 05C05, 90C27 © 2025, CC BY.

关键词： graph algorithms