Zobrazeno 1 - 10
of 54
pro vyhledávání: '"Kuhnert, Sebastian"'
Publikováno v:
In Organic Geochemistry March 2023 177
Autor:
Kuhnert, Sebastian
Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekann
Externí odkaz:
http://edoc.hu-berlin.de/18452/18099
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given grap
Externí odkaz:
http://arxiv.org/abs/1709.10063
Autor:
Warner, Wiebke, Zeman-Kuhnert, Sebastian, Heim, Christine, Nachtigall, Solveig, Licha, Tobias
Publikováno v:
In Chemosphere October 2021 281
In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computin
Externí odkaz:
http://arxiv.org/abs/1606.04383
Publikováno v:
Information and Computation 247 (2016), pp. 266-277
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular ar
Externí odkaz:
http://arxiv.org/abs/1402.4642
A circular-arc hypergraph $H$ is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is an arc of consecutive vertices. An arc ordering is tight if, for any two hyperedges $A$ and $B
Externí odkaz:
http://arxiv.org/abs/1312.1172
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are equal. This implies that the recognition and the isomorphism problems f
Externí odkaz:
http://arxiv.org/abs/1202.4406
Publikováno v:
In Discrete Applied Mathematics 30 January 2017 217 Part 2:220-228
Publikováno v:
In Journal of Discrete Algorithms May-November 2016 38-41:38-49