Zobrazeno 1 - 10
of 1 042
pro vyhledávání: '"68R05"'
Given $n$ buttons and $n$ bulbs so that the $i$th button toggles the $i$th bulb and perhaps some other bulbs, we compute the sharp lower bound on the number of bulbs that can be lit regardless of the action of the buttons. In the previous article we
Externí odkaz:
http://arxiv.org/abs/2410.02460
We study two positional numeration systems which are known for allowing very efficient addition and multiplication of complex numbers. The first one uses the base $\beta = \imath - 1$ and the digit set $\mathcal{D} = \{ 0, \pm 1, \pm \imath \}$. In t
Externí odkaz:
http://arxiv.org/abs/2410.02418
Autor:
Roucairol, Milo, Cazenave, Tristan
We are interested in the automatic refutation of spectral graph theory conjectures. Most existing works address this problem either with the exhaustive generation of graphs with a limited size or with deep reinforcement learning. Exhaustive generatio
Externí odkaz:
http://arxiv.org/abs/2409.18626
Autor:
Buchbinder, Niv, Feldman, Moran
Maximization of submodular functions under various constraints is a fundamental problem that has been studied extensively. A powerful technique that has emerged and has been shown to be extremely effective for such problems is the following. First, a
Externí odkaz:
http://arxiv.org/abs/2409.14325
We introduce the game of Cat Herding, where an omnipresent herder slowly cuts down a graph until an evasive cat player has nowhere to go. The number of cuts made is the score of a game, and we study the score under optimal play. In this paper, we beg
Externí odkaz:
http://arxiv.org/abs/2409.13685
The $\lambda$-backbone coloring of the graph $G$ with backbone $H$ is a graph-coloring problem in which we are given a graph $G$ and a subgraph $H$, and we want to assign colors to vertices in such a way that the endpoints of every edge from $G$ have
Externí odkaz:
http://arxiv.org/abs/2409.10201
Genome rearrangements are events in which large blocks of DNA exchange pieces during evolution. The analysis of such events is a tool for understanding evolutionary genomics, based on finding the minimum number of rearrangements to transform one geno
Externí odkaz:
http://arxiv.org/abs/2409.09734
A graph class admits an implicit representation if, for every positive integer $n$, its $n$-vertex graphs have a $O(\log n)$-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length $O(\log n)$ such that the pr
Externí odkaz:
http://arxiv.org/abs/2409.04821
Autor:
Eidi, Marzieh, Mukherjee, Sayan
Bipartite graphs are a fundamental concept in graph theory and have significant applications in data analysis and modeling complex processes. A graph is bipartite if its vertices can be divided into two sets, with no connections within each set. Dete
Externí odkaz:
http://arxiv.org/abs/2409.00682
Autor:
Cervantes, Jillian, Harris, Pamela E.
For a pair of positive integer parameters $(t,r)$, a subset $T$ of vertices of a graph $G$ is said to $(t,r)$ broadcast dominate a graph $G$ if, for any vertex $u$ in $G$, we have $\sum_{v\in T, u\in N_t(v)}(t-d(u,v))\geq r$, where where $N_{t}(v)=\{
Externí odkaz:
http://arxiv.org/abs/2408.13331