Zobrazeno 1 - 10
of 573
pro vyhledávání: '"Yeo, Anders"'
An oriented multigraph is a directed multigraph without directed 2-cycles. Let ${\rm fas}(D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$. The degree of a vertex is the sum of its out- and in-degrees. In several papers
Externí odkaz:
http://arxiv.org/abs/2409.07680
A run of the deferred acceptance (DA) algorithm may contain proposals that are sure to be rejected. We introduce the accelerated deferred acceptance algorithm that proceeds in a similar manner to DA but with sure-to-be rejected proposals ruled out. A
Externí odkaz:
http://arxiv.org/abs/2409.06865
An oriented graph $D$ is converse invariant if, for any tournament $T$, the number of copies of $D$ in $T$ is equal to that of its converse $-D$. El Sahili and Ghazo Hanna [J. Graph Theory 102 (2023), 684-701] showed that any oriented graph $D$ with
Externí odkaz:
http://arxiv.org/abs/2407.17051
It is well-known and easy to show that even the following version of the directed travelling salesman problem is NP-complete: Given a strongly connected complete digraph $D=(V,A)$, a cost function $w: A\rightarrow \{0,1\}$ and a natural number $K$; d
Externí odkaz:
http://arxiv.org/abs/2403.07597
A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of edge-weighted graphs with bounded maximum degree. Our results improve a
Externí odkaz:
http://arxiv.org/abs/2401.10074
In 1981, Bermond and Thomassen conjectured that for any positive integer $k$, every digraph with minimum out-degree at least $2k-1$ admits $k$ vertex-disjoint directed cycles. In this short paper, we verify the Bermond-Thomassen conjecture for triang
Externí odkaz:
http://arxiv.org/abs/2311.13369
In order to coordinate players in a game must first identify a target pattern of behaviour. In this paper we investigate the difficulty of identifying prominent outcomes in two kinds of binary action coordination problems in social networks: pure coo
Externí odkaz:
http://arxiv.org/abs/2311.03195
We introduce and study a new optimization problem on digraphs, termed Maximum Weighted Digraph Partition (MWDP) problem. We prove three complexity dichotomies for MWDP: on arbitrary digraphs, on oriented digraphs, and on symmetric digraphs. We demons
Externí odkaz:
http://arxiv.org/abs/2307.01109
For a vertex $x$ of a digraph, $d^+(x)$ ($d^-(x)$, resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++}(x)$ is the number of vertices at distance 2 from $x$. In 1995, Seymour conjectured that for any oriented graph $D$ ther
Externí odkaz:
http://arxiv.org/abs/2306.03493
We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in
Externí odkaz:
http://arxiv.org/abs/2305.07124