Zobrazeno 1 - 10
of 55 808
pro vyhledávání: '"science and mathematics"'
An injective colouring of a graph is a colouring in which every two vertices sharing a common neighbour receive a different colour. Chen, Hahn, Raspaud and Wang conjectured that every planar graph of maximum degree $\Delta \ge 3$ admits an injective
Externí odkaz:
http://arxiv.org/abs/2412.09969
Homophily is a graph property describing the tendency of edges to connect similar nodes. There are several measures used for assessing homophily but all are known to have certain drawbacks: in particular, they cannot be reliably used for comparing da
Externí odkaz:
http://arxiv.org/abs/2412.09663
A graph G is c-closed if every two vertices with at least c common neighbors are adjacent to each other. Introduced by Fox, Roughgarden, Seshadhri, Wei and Wein [ICALP 2018, SICOMP 2020], this definition is an abstraction of the triadic closure prope
Externí odkaz:
http://arxiv.org/abs/2412.09567
Autor:
Kaymakov, K. V., Malyshev, D. S.
In this paper, we consider the minimum spanning tree problem (for short, MSTP) on an arbitrary set of $n$ points of $d$-dimensional space in $l_1$-norm. For this problem, for each fixed $d\geq 2$, there is a known algorithm of the computational compl
Externí odkaz:
http://arxiv.org/abs/2412.08584
Autor:
Martin, Sébastien
This manuscript describes the notions of blocker and interdiction applied to well-known optimization problems. The main interest of these two concepts is the capability to analyze the existence of a combinatorial structure after some modifications. W
Externí odkaz:
http://arxiv.org/abs/2412.08256
Autor:
Kupavskii, Andrey
We say that a family of $k$-subsets of an $n$-element set is {\it intersecting}, if any two of its sets intersect. In this paper, we study the structure of large intersecting families. Several years ago, Han and Kohayakawa (Proc. AMS, 2017), and then
Externí odkaz:
http://arxiv.org/abs/2412.07974
Autor:
Akbay, Mehmet Anıl, Blum, Christian
The growing need for sustainable logistics solutions has led to the evolution of vehicle routing problems (VRPs) into more complex variants that address modern challenges. Among these, the Two-Echelon Electric Vehicle Routing Problem (2E-EVRP) has em
Externí odkaz:
http://arxiv.org/abs/2412.06671
The Steiner Forest problem is an important generalization of the Steiner Tree problem. We are given an undirected graph with nonnegative edge costs and a collection of pairs of vertices. The task is to compute a cheapest forest with the property that
Externí odkaz:
http://arxiv.org/abs/2412.06518
The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs' generalization abilities -- making meaningful predictions
Externí odkaz:
http://arxiv.org/abs/2412.07106
Autor:
Boykett, Tim
Permutation clones generalise permutation groups and clone theory. We investigate permutation clones defined by relations, or equivalently, the automorphism groups of powers of relations. We find many structural results on the lattice of all relation
Externí odkaz:
http://arxiv.org/abs/2412.06109