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

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

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

Hosoya Polynomials of Mycielskian graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Vaidya, Sanju Li, Aihua Mercy College Dobbs FerryNY555 United States Montclair State University 1 Normal Avenue MontclairNJ07044 United States

Vulnerability measures and topological indices are crucial in solving various problems such as the stability of the communication networks and development of mathematical models for chemical compounds. In 1947, Harry Wiener introduced a topological index related to molecular branching. Since then, more than 100 topological indices for graphs were introduced. Many graph polynomials play important roles in measuring such indices. Hosoya polynomial is among many of them. Introduced by Hosoya in 1988, the Hosoya polynomial of a given graph G is a polynomial with the coefficients being the numbers of pairs of vertices in G with all possible distances. For a given graph G, an extension graph is called Mycielskian graph of G, defined by Mycielski in 1955. In this paper, we investigate relationships between the Hosoya polynomial of any graph and that of its Mycielskian graph. The results are applied to compute the vulnerability measures, closeness and betweenness centrality, and the extended Wiener indices of selected graphs and their Mycielskian graphs. In the network science, these measures are commonly used to describe certain connectivity properties of a network. It is fascinating to see how graph polynomials are useful in other scientific *** Codes 05C31, 05C12, 05C09 © 2025, CC0.

关键词： graph algorithms

Critical (P5, W4)-Free graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Xia, Wen Jooken, Jorik Goedgebeur, Jan Beaton, Iain Cameron, Ben Huang, Shenwei College of Computer Science Nankai University Tianjin300071 China Tianjin Key Laboratory of Network and Data Security Technology Nankai University Tianjin300071 China Department of Computer Science KU Leuven Campus Kulak-Kortrijk Kortrijk8500 Belgium Department of Applied Mathematics Computer Science and Statistics Ghent University Ghent9000 Belgium Department of Mathematics and Statistics Acadia University WolfvilleNS Canada School of Mathematical and Computational Sciences University of Prince Edward Island CharlottetownPE Canada

A graph G is k-vertex-critical if χ(G) = k but χ(G − v) 1, H2)-free if it contains no induced subgraph isomorphic to H1 nor H2. A W4 is the graph consisting of a C4 plus an additional vertex adjacent to all the vertices of the C4. We show that there are finitely many k-vertex-critical (P5, W4)-free graphs for all k ≥ 1 and we characterize all 5-vertex-critical (P5, W4)-free graphs. Our results imply the existence of a polynomial-time certifying algorithm to decide the k-colorability of (P5, W4)-free graphs for each k ≥ 1 where the certificate is either a k-coloring or a (k + 1)-vertex-critical induced subgraph. Copyright © 2025, The Authors. All rights reserved.

关键词： 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