TY - JOUR A1 - Göbel, Andreas A1 - Lagodzinski, Gregor J. A. A1 - Seidel, Karen T1 - Counting homomorphisms to trees modulo a prime JF - ACM transactions on computation theory : TOCT / Association for Computing Machinery N2 - Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #(p) HOMSTOH, the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p. Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies.
Our main result states that for every tree H and every prime p the problem #pHOMSTOH is either polynomial time computable or #P-p-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of #pHOMSTOH are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p. These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p. KW - Graph homomorphisms KW - modular counting KW - complexity dichotomy Y1 - 2021 U6 - https://doi.org/10.1145/3460958 SN - 1942-3454 SN - 1942-3462 VL - 13 IS - 3 SP - 1 EP - 33 PB - Association for Computing Machinery CY - New York ER - TY - JOUR A1 - Hohmann, Andreas A1 - Diercks, B. A1 - Lühnenschloß, D. A1 - Seidel, Ilka A1 - Griebsch, A. T1 - The structure of physical abilities in sprint running Y1 - 1999 ER - TY - JOUR A1 - Hohmann, Andreas A1 - Diercks, B. A1 - Lühnenschloß, D. A1 - Seidel, Ilka A1 - Wichmann, E. T1 - Criteria of talent in sport Y1 - 1999 ER - TY - JOUR A1 - Pinkernelle, Josephine A1 - Abraham, Andreas A1 - Seidel, Katja A1 - Braun, Katharina T1 - Paternal deprivation induces dendritic and synaptic changes and hemispheric asymmetry of pyramidal neurons in the somatosensory cortex N2 - Similar to maternal care, paternal care is a source of neonatal sensory stimulation, which in primates and rodents has been shown to be essential for developing structure and function of sensory cortices. The aim of our study in the biparental rodent Octodon degus was to assess the impact of paternal deprivation on dendritic and synaptic development in the somatosensory cortex. We (i) quantified the amount of paternal care in relation to total parental investment and (ii) compared dendritic and synaptic development of pyramidal neurons in the somatosensory cortex of animals raised by a single mother or by both parents. On the behavioral level we show that paternal care comprises 37% of total parent-offspring interactions, and that the somatosensory stimulation provided by the fathers primarily consists of huddling, licking/grooming, and playing. On the morphological level we found that, compared with offspring raised by both parents (mother and father), the father-deprived animals displayed significantly reduced spine numbers on the basal dendrites of pyramidal neurons. Furthermore, paternal deprivation induces hemispheric asymmetry of the dendritic morphology of somatosensory pyramidal neurons. Father-deprived animals show shorter and less complex basal dendrites in the left somatosensory cortex compared with the right hemisphere. These findings indicate that paternal deprivation results in delayed or retarded dendritic and synaptic development of somatosensory circuits. Y1 - 2009 UR - http://www3.interscience.wiley.com/cgi-bin/jhome/114030483 U6 - https://doi.org/10.1002/Dneu.20726 SN - 1932-8451 ER - TY - JOUR A1 - Tarasova, Larisa A1 - Merz, Ralf A1 - Kiss, Andrea A1 - Basso, Stefano A1 - Blöchl, Günter A1 - Merz, Bruno A1 - Viglione, Alberto A1 - Plötner, Stefan A1 - Guse, Björn A1 - Schumann, Andreas A1 - Fischer, Svenja A1 - Ahrens, Bodo A1 - Anwar, Faizan A1 - Bárdossy, András A1 - Bühler, Philipp A1 - Haberlandt, Uwe A1 - Kreibich, Heidi A1 - Krug, Amelie A1 - Lun, David A1 - Müller-Thomy, Hannes A1 - Pidoto, Ross A1 - Primo, Cristina A1 - Seidel, Jochen A1 - Vorogushyn, Sergiy A1 - Wietzke, Luzie T1 - Causative classification of river flood events JF - Wiley Interdisciplinary Reviews : Water N2 - A wide variety of processes controls the time of occurrence, duration, extent, and severity of river floods. Classifying flood events by their causative processes may assist in enhancing the accuracy of local and regional flood frequency estimates and support the detection and interpretation of any changes in flood occurrence and magnitudes. This paper provides a critical review of existing causative classifications of instrumental and preinstrumental series of flood events, discusses their validity and applications, and identifies opportunities for moving toward more comprehensive approaches. So far no unified definition of causative mechanisms of flood events exists. Existing frameworks for classification of instrumental and preinstrumental series of flood events adopt different perspectives: hydroclimatic (large-scale circulation patterns and atmospheric state at the time of the event), hydrological (catchment scale precipitation patterns and antecedent catchment state), and hydrograph-based (indirectly considering generating mechanisms through their effects on hydrograph characteristics). All of these approaches intend to capture the flood generating mechanisms and are useful for characterizing the flood processes at various spatial and temporal scales. However, uncertainty analyses with respect to indicators, classification methods, and data to assess the robustness of the classification are rarely performed which limits the transferability across different geographic regions. It is argued that more rigorous testing is needed. There are opportunities for extending classification methods to include indicators of space-time dynamics of rainfall, antecedent wetness, and routing effects, which will make the classification schemes even more useful for understanding and estimating floods. This article is categorized under: Science of Water > Water Extremes Science of Water > Hydrological Processes Science of Water > Methods KW - flood genesis KW - flood mechanisms KW - flood typology KW - historical floods KW - hydroclimatology of floods Y1 - 2019 U6 - https://doi.org/10.1002/wat2.1353 SN - 2049-1948 VL - 6 IS - 4 PB - Wiley CY - Hoboken ER -