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

A well-separated pair decomposition for low density graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Gudmundsson, Joachim Wong, Sampson

Low density graphs are considered to be a realistic graph class for modelling road networks. It has advantages over other popular graph classes for road networks, such as planar graphs, bounded highway dimension graphs, and spanners. We believe that low density graphs have the potential to be a useful graph class for road networks, but until now, its usefulness is limited by a lack of available tools. In this paper, we develop two fundamental tools for low density graphs, that is, a well-separated pair decomposition and an approximate distance oracle. We believe that by expanding the algorithmic toolbox for low density graphs, we can help provide a useful and realistic graph class for road networks, which in turn, may help explain the many efficient and practical heuristics available for road networks. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

Filling some gaps on the edge coloring problem of split graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Couto, Fernanda Ferraz, Diego Amaro Klein, Sulamita Federal Rural University of Rio de Janeiro Nova Iguaçu Brazil Federal University of Rio de Janeiro Rio de Janeiro Brazil

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. A connected graph G is said to be t-admissible if admits a spanning tree in which the distance between any two adjacent vertices of G is at most t. Given a graph G, determining the smallest t for which G is t-admissible, i.e., the stretch index of G denoted by σ(G), is the goal of the t-admissibility problem. Split graphs are 3-admissible and can be partitioned into three subclasses: split graphs with σ = 1,2 or 3. In this work we consider such a partition while dealing with the problem of coloring the edges of a split graph. Vizing proved that any graph can have its edges colored with ∆ or ∆+1 colors, and thus can be classified as Class 1 or Class 2, respectively. The edge coloring problem is open for split graphs in general. In previous results, we classified split graphs with σ = 2 and in this paper we classify and provide an algorithm to color the edges of a subclass of split graphs with σ = 3. © 2024, CC BY.

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

A unified approach for domination and packing problems in graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Hinrichsen, E. Nasini, G. Vansteenkiste, N. Universidad Nacional de Rosario Rosario Argentina CONICET Rosario Argentina

In this paper, we introduce new concepts of domination and packing functions in graphs, which generalize, respectively, the labelled dominating and packing functions defined by Lee and Chang in 2008, and Hinrichsen et al. in 2019. These generalized functions offer a unified and simpler framework for addressing many of the variations of domination and packing concepts in graphs explored in the literature. Interestingly, their associated optimization problems turn out to be equivalent, providing insight to explain the observed coincidences in computational complexity results for graph classes where both problems, the domination one and its corresponding packing variation, have been analyzed. This equivalence also allows us to solve some computational complexity open questions, for some graph classes. Furthermore, we prove that the generalized problems remain solvable in polynomial time for graphs with bounded clique-width and strongly chordal graphs. © 2025, CC BY.

关键词： graph algorithms

PROFILE AND NEIGHBOURHOOD COMPLEXITY OF graphS WITH EXCLUDED MINORS AND TREE-STRUCTURED graphS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Beaudou, Laurent Bok, Jan Foucaud, Florent Quiroz, Daniel A. Raymond, Jean-Florent Université Clermont Auvergne CNRS Clermont Auvergne INP Mines Saint-Étienne LIMOS Clermont-Ferrand63000 France Department of Algebra Faculty of Mathematics and Physics Charles University Sokolovská 83 Prague 818675 Czech Republic Instituto de Ingeniería Matemática Centro de Investigación y Mode-lamiento de Fenómenos Aleatorios - Valparaíso CIMFAV Universidad de Valparaíso Valparaíso Chile Univ. Lyon CNRS ENS de Lyon Université Claude Bernard Lyon 1 LIP UMR5668 Lyon France

The r-neighbourhood complexity of a graph G is the function counting, for a given integer k, the largest possible number, over all vertex-subsets A of size k, of subsets of A realized as the intersection between the r-neighbourhood of some vertex and A. A refinement of this notion is the r-profile complexity, that counts the maximum number of distinct distance-vectors from any vertex to the vertices of A, ignoring distances larger than r. Typically, in structured graph classes such as graphs of bounded VC-dimension or chordal graphs, these functions are bounded, leading to insights into their structural properties and efficient algorithms. We improve existing bounds on the r-profile complexity (and thus on the r-neighbourhood complexity) for graphs in several structured graph classes. We show that the r-profile complexity of graphs excluding Kh as a minor is in Oh(r3h−3k). For graphs of treewidth at most t, we give a bound in Ot(rt+1k), which is tight up to a function of t as a factor. These bounds improve results of Joret and Rambaud and answer a question of their paper [Combinatorica, 2024]. We also apply our methods to other classes of bounded expansion such as graphs excluding a fixed complete graph as a subdivision. For outerplanar graphs, we can improve our treewidth bound by a factor of r and conjecture that a similar improvement holds for graphs with bounded simple treewidth. For graphs of treelength at most , we give the upper bound of O(k(r2( + 1)k)), which we improve to O (k · (r2k + r2k2)) in the case of chordal graphs and O(k2r) for interval graphs. Our bounds also imply relations between the order, diameter and metric dimension of graphs in these classes, improving results from [Beaudou et al., SIDMA 2017]. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Towards Optimal Distributed Delta Coloring

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jakob, Manuel Maus, Yannic

The ∆-vertex coloring problem has become one of the prototypical problems for understanding the complexity of local distributed graph problems on constant-degree graphs. The major open problem is whether the problem can be solved deterministically in logarithmic time, which would match the lower bound [Chang et al., FOCS’16]. Despite recent progress in the design of efficient ∆-coloring algorithms, there is currently a polynomial gap between the upper and lower bounds. In this work we present a O(log n)-round deterministic ∆-coloring algorithm for dense constant-degree graphs, matching the lower bound for the problem on general graphs. For general ∆ the algorithms’ complexity is min{Oe(log5/3 n), O(∆ + log n)}. All recent distributed and sublinear graph coloring algorithms (also for coloring with more than ∆ colors) decompose the graph into sparse and dense parts. Our algorithm works for the case that this decomposition has no sparse vertices. Ironically, in recent (randomized) ∆-coloring algorithms, dealing with sparse parts was relatively easy and these dense parts arguably posed the major hurdle. We present a solution that addresses the dense parts and may have the potential for extension to sparse parts. Our approach is fundamentally different from prior deterministic algorithms and hence hopefully contributes towards designing an optimal algorithm for the general case. Additionally, we leverage our result to also obtain a randomized min{Oe(log5/3 log n), O(∆ + log log n)}-round algorithm for ∆-coloring dense graphs that also matches the lower bound for the problem on general constant-degree graphs [Brandt et al.;STOC’16]. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Representation Number of Word-Representable Split graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Dwary, Tithi Mozhui, Khyodeno Krishna, K.V. Indian Institute of Technology Guwahati India

A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. The word-representability of split graphs was studied in a series of papers in the literature, and the class of word-representable split graphs was characterized through semi-transitive orientation. Nonetheless, the representation number of this class of graphs is still not known. In general, determining the representation number of a word-representable graph is an NP-complete problem. In this work, through an algorithmic procedure, we show that the representation number of the class of word-representable split graphs is at most three. Further, we characterize the class of word-representable split graphs as well as the class of split comparability graphs which have representation number exactly three. © 2025, CC BY.

关键词： graph algorithms

On the Complexity of Minimising the Moving Distance for Dispersing Objects

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Honorato-Droguett, Nicolás Kurita, Kazuhiro Hanaka, Tesshu Ono, Hirotaka Nagoya University Japan Kyushu University Japan

We study Geometric graph Edit Distance (GGED), a graph-editing model to compute the minimum edit distance of intersection graphs that uses moving objects as an edit operation. We first show an O(n log n)-time algorithm that minimises the total moving distance to disperse unit intervals. This algorithm is applied to render a given unit interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. We next show that GGED becomes strongly NP-hard when rendering a weighted interval graph (i) edgeless, (ii) acyclic and (iii) k-clique-free. Lastly, we prove that minimising the maximum moving distance for rendering a unit disk graph edgeless is strongly NP-hard over the L1 and L2 distances. © 2025, CC BY.

关键词： graph algorithms

FLUCTUATIONS OF THE GIANT OF POISSON RANDOM graphS

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Clancy, David University of Wisconsin Department of Mathematics United States

Enriquez, Faraud, and Lemaire (2023) have established process-level fluctuations for the giant of the dynamic Erdős-Rényi random graph above criticality and show that the limit is a centered Gaussian process with continuous sample paths. A random walk proof was recently obtained by Corujo, Limic and Lemaire (2024). We show that a similar result holds for rank-one inhomogeneous models whenever the empirical weight distribution converges to a limit and its second moment converges as *** Codes 60F17, 05C80 Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms