Expected reliability of communication protocols

Autor: Janina Silvana P. Patno, André Kündgen

Publikováno v: Discrete Mathematics. 342:2867-2874

We consider the problem of sending a message from a sender s to a receiver r through an unreliable network by specifying in a protocol what each vertex is supposed to do if it receives the message from one of its neighbors. A protocol for routing a m

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::c4322219a4e97bd634aa4ea8929778f6
https://doi.org/10.1016/j.disc.2018.12.013

Fractional cocoloring of graphs

Autor: John Gimbel, André Kündgen, Michael Molloy

The cochromatic number $Z(G)$ of a graph $G$ is the fewest number of colors needed to color the vertices of $G$ so that each color class is a clique or an independent set. In a fractional cocoloring of $G$ a non-negative weight is assigned to each cl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::dd43c0a995fb224fd6ba003a8f2be315
http://arxiv.org/abs/1906.05504

Fractional coloring methods with applications to degenerate graphs and graphs on surfaces

Autor: Binlong Li, John Gimbel, Carsten Thomassen, André Kündgen

Publikováno v: Gimbel, J, Kündgen, A, Li, B & Thomassen, C 2019, ' Fractional coloring methods with applications to degenerate graphs and graphs on surfaces ', SIAM Journal on Discrete Mathematics, vol. 33, no. 3, pp. 1415-1430 . https://doi.org/10.1137/18M1177317

We study methods for finding strict upper bounds on the fractional chromatic number χf(G) of a graph G. We illustrate these methods by providing short proofs of known inequalities in connection with Grötzsch’s 3-color theorem and the 5-color theo

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::93f900cf71499bcea998ebcd84645f61
https://orbit.dtu.dk/en/publications/b63bb9a2-d302-4547-b82c-a44271c2f4af

On 2-factors with long cycles in cubic graphs

Autor: André Kündgen, R. Bruce Richter

Publikováno v: Ars Mathematica Contemporanea. 4:79-93

Every 2-connected cubic graph G has a 2-factor, and much effort has gone into studying conditions that guarantee G to be Hamiltonian. We show that if G is not Hamiltonian, then G is either the Petersen graph or contains a 2-factor with a cycle of len

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::e3bfda7a06adb5fbede2900eef3343fe
https://doi.org/10.26493/1855-3974.194.abe

k-Robust Single-Message Transmission

Autor: Michael J. Pelsmajer, Radhika Ramamurthi, André Kündgen

Publikováno v: SIAM Journal on Discrete Mathematics. 24:301-321

We consider the problem of transmitting a message from a sender $s$ to a receiver $r$ through a network in which edges may fail and cannot recover. In the transmission protocols we consider, we require that $r$ may not be “flooded” by infinitely

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::371fb56f8879c61e3539bd24f7b28939
https://doi.org/10.1137/070689802