Zobrazeno 1 - 10
of 13
pro vyhledávání: '"Lilla Tóthmérész"'
Publikováno v:
Discrete Mathematics, 346 (9)
Discrete Mathematics, 346 (9)
ISSN:0012-365X
ISSN:1872-681X
ISSN:0012-365X
ISSN:1872-681X
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::89fb2ed76d48526e6a59af5dfbf381b0
https://hdl.handle.net/20.500.11850/615024
https://hdl.handle.net/20.500.11850/615024
Autor:
Tamás Kálmán, Lilla Tóthmérész
Publikováno v:
Mathematika. 68:1176-1220
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3fd012d89f2015a57d55a48c71115be1
https://doi.org/10.1112/mtk.12163
https://doi.org/10.1112/mtk.12163
Autor:
Lilla Tóthmérész, Bálint Hujter
Publikováno v:
European Journal of Combinatorics. 78:90-104
Baker and Norine proved a Riemann--Roch theorem for divisors on undirected graphs. The notions of graph divisor theory are in duality with the notions of the chip-firing game of Bj\"orner, Lov\'asz and Shor. We use this connection to prove Riemann--R
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5fd4deba2443e50232d87a1ddda6c940
https://doi.org/10.1016/j.ejc.2019.01.007
https://doi.org/10.1016/j.ejc.2019.01.007
Autor:
Lilla Tóthmérész
Publikováno v:
European Journal of Combinatorics. 101:103466
Chip-firing and rotor-routing are two well-studied examples of abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a sim
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f0b03fc2c1a29c726aaff951ce24e2a0
https://doi.org/10.1016/j.ejc.2021.103466
https://doi.org/10.1016/j.ejc.2021.103466
Autor:
Lilla Tóthmérész
Publikováno v:
Discrete Applied Mathematics. 236:428-437
We define the analogue of linear equivalence of graph divisors for the rotor-router model, and use it to prove polynomial time computability of some problems related to rotor-routing. Using the connection between linear equivalence for chip-firing an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c52fa943b81ec223d00c276eb80277e0
https://doi.org/10.1016/j.dam.2017.11.008
https://doi.org/10.1016/j.dam.2017.11.008
Baker and Wang define the so-called Bernardi action of the sandpile group of a ribbon graph on the set of its spanning trees. This potentially depends on a fixed vertex of the graph but it is independent of the base vertex if and only if the ribbon s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::00397c529fe6ed9bf168ecdc6627c836
http://arxiv.org/abs/1905.01689
http://arxiv.org/abs/1905.01689
We introduce the notion of semibreak divisors on metric graphs (tropical curves) and prove that every effective divisor class (of degree at most the genus) has a semibreak divisor representative. This appropriately generalizes the notion of break div
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3391ab0c9801291eb492c58ea065f35d
http://arxiv.org/abs/1807.00843
http://arxiv.org/abs/1807.00843
Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
Autor:
Viktor Kiss, Lilla Tóthmérész
Publikováno v:
Discrete Applied Mathematics. 193:48-56
Baker and Norine introduced a graph-theoretic analogue of the Riemann–Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing the rank of a divisor on a graph is NP -hard, even for simple graphs.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9dbabfe2aeafafb7d8a20a63e55c331f
https://doi.org/10.1016/j.dam.2015.04.030
https://doi.org/10.1016/j.dam.2015.04.030
Autor:
Lilla Tóthmérész, Zoltán Király
Publikováno v:
Scopus-Elsevier
A famous conjecture (usually called Ryser's conjecture) that appeared in the PhD thesis of his student, J. R. Henderson, states that for an $r$-uniform $r$-partite hypergraph $\mathcal{H}$, the inequality $\tau(\mathcal{H})\le(r-1)\!\cdot\! \nu(\math
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2fffa78e989e44a424dd3417c4b7cdd3
https://doi.org/10.37236/6448
https://doi.org/10.37236/6448
Publikováno v:
P AM MATH SOC PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY.
In this paper, we study the complexity of the chip-firing reachability problem. We show that for Eulerian digraphs, the reachability problem can be decided in strongly polynomial time, even if the digraph has multiple edges. We also show a special ca
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ac9cec0f766a22ab91763d832777c342
http://hdl.handle.net/10831/48818
http://hdl.handle.net/10831/48818