Zobrazeno 1 - 10
of 561
pro vyhledávání: '"A, Jedlicková"'
Autor:
Jedličková, Nikola, Kratochvíl, Jan
A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path) in an input graph are well known to be NP-complete, and restricted cl
Externí odkaz:
http://arxiv.org/abs/2403.03668
Autor:
Jedličková, Nikola, Kratochvíl, Jan
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph are well-known to be NP-complete, in fact, they belong to the first p
Externí odkaz:
http://arxiv.org/abs/2309.09228
The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees and reflexive signed graphs. Irreflexive signed graphs are in a certain sense t
Externí odkaz:
http://arxiv.org/abs/2306.06449
The notion of graph covers is a discretization of covering spaces introduced and deeply studied in topology. In discrete mathematics and theoretical computer science, they have attained a lot of attention from both the structural and complexity persp
Externí odkaz:
http://arxiv.org/abs/2306.06431
Distribution crises are manifested by a great discrepancy between the demand and the supply of a critically important good, for a period of time. In this paper, we suggest a hybrid market mechanism for minimising the negative consequences of sudden d
Externí odkaz:
http://arxiv.org/abs/2207.00898
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Signed graphs arise naturally in many contexts,
Externí odkaz:
http://arxiv.org/abs/2206.01068
Publikováno v:
In Discrete Applied Mathematics 31 December 2024 359:229-243
In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain {\em multiple edges}, {\em loops}, and {\em semi-edges}. A graph is called {\em simple} if it contains no semi-edges, no
Externí odkaz:
http://arxiv.org/abs/2204.04280
Publikováno v:
In Theoretical Computer Science 27 June 2024 1001
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a
Externí odkaz:
http://arxiv.org/abs/2103.15214