• A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Lima, Paloma T.; Jaffke, Lars (Journal article; Peer reviewed, 2020)
      A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...
    • A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Jaffke, Lars; Lima, Paloma T. (Peer reviewed; Journal article, 2019-08-20)
      A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...
    • Complexity of the Steiner Network Problem with Respect to the Number of Terminals 

      Eiben, Eduard; Knop, Dusan; Panolan, Fahad; Suchý, Ondřej (Journal article; Peer reviewed, 2019)
      In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ...
    • Composition of multilevel domain-specific modelling languages 

      Rodríguez, Alejandro; Macias Gomez de Villar, Fernando; Durán, Francisco; Rutle, Adrian; Wolter, Uwe Egbert (Journal article; Peer reviewed, 2023)
      Multilevel Modelling (MLM) approaches make it possible for designers and modellers to work with an unlimited number of abstraction levels to specify their domain-specific modelling languages (DSMLs). To fully exploit MLM ...
    • Compressing permutation groups into grammars and polytopes. A graph embedding approach 

      Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)
      It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...
    • Computation of Treespan. A Generalization of Bandwidth to Treelike Structures 

      Dregi, Markus Sortland (Master thesis, 2012-06-14)
      Motivated by a search game, Fomin, Heggernes and Telle [Algorithmica, 2005] defined the graph parameter treespan, a generalization of the well studied parameter bandwidth. Treespan is the maximum number of appearances of ...
    • Computational analysis of the evolutionary dynamics of proteins on a genomic scale 

      Hughes, Timothy (Doctoral thesis, 2007-01-16)
      Biology is primarily concerned with the study of all phenotypic aspects of living organisms and evolutionary biology is more specifically interested in elucidating how different phenotypes evolved. Proteins (and RNA ...
    • Computational complexity aspects of super domination 

      Bujtás, Csilla; Ghanbari, Nima; Klavžar, Sandi (Journal article; Peer reviewed, 2023)
      Let G be a graph. A dominating set D ⊆ V (G) is a super dominating set if for every vertex x ∈ V (G) \ D there exists y ∈ D such that NG (y) ∩ (V (G) \ D)) = {x}. The cardinality of a smallest super dominating set of G is ...
    • Computational Science in the 17th Century. Numerical Solution of Algebraic Equations: Digit–by–Digit Computation 

      Steihaug, Trond (Chapter, 2022)
      In this paper we give a complete overview of test–problems by Viète from 1600, Harriot from 1631 and Oughtred from 1647. The original material is not easily accessible due to archaic language and lack of conciseness. Viéte’s ...
    • Computational science in the eighteenth century. Test cases for the methods of Newton, Raphson, and Halley: 1685 to 1745 

      Steihaug, Trond (Peer reviewed; Journal article, 2020)
      This is an overview of examples and problems posed in the late 1600s up to the mid 1700s for the purpose of testing or explaining the two different implementations of the Newton-Raphson method, Newton’s method as described ...
    • Computing Connected Components on Multiple GPUs 

      Hellås, Yngve (Master thesis, 2018-12-19)
      We look at multiple GPU programming, using the connected components algorithm as the basis when we look into libraries and runtime environment for multiple GPU programming. We also show that Rem is a fast parallel algorithm, ...
    • Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings 

      Pilipczuk, Michal Pawel (Peer reviewed; Journal article, 2013)
      The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ...
    • Computing minimal triangulation in Time o(n^2.376) 

      Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve (Journal article, 2005)
    • Connecting the Dots (with Minimum Crossings) 

      Agrawal, Akanksha; Guspiel, Grzegorz; Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
      We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...
    • Connecting Vertices by Independent Trees 

      Basavaraju, Manu; Fomin, Fedor; Golovach, Petr; Saurabh, Saket (Journal article; Peer reviewed, 2014)
      We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...
    • Conserved BK Channel-Protein Interactions Reveal Signals Relevant to Cell Death and Survival 

      Sokolowski, Bernd; Orchard, Sandra; Harvey, Margaret; Sridhar, Settu; Sakai, Yoshihisa (Peer reviewed; Journal article, 2011-12-09)
      The large-conductance Ca2+-activated K+ (BK) channel and its b-subunit underlie tuning in non-mammalian sensory or hair cells, whereas in mammals its function is less clear. To gain insights into species differences and ...
    • Considering Best Practices in Color Palettes for Molecular Visualizations 

      Garrison, Laura Ann; Bruckner, Stefan (Journal article; Peer reviewed, 2022)
      Biomedical illustration and visualization techniques provide a window into complex molecular worlds that are difficult to capture through experimental means alone. Biomedical illustrators frequently employ color to help ...
    • Consistency of Heterogeneously Typed Behavioural Models: A Coalgebraic Approach 

      Wolter, Uwe Egbert; König, Harald (Journal article; Peer reviewed, 2022)
      Systematic and formally underpinned consistency checking of heterogeneously typed interdependent behavioural models requires a common metamodel, into which the involved models can be translated. And, if additional system ...
    • Constructing APN functions through isotopic shifts 

      Budaghyan, Lilya; Calderini, Marco; Carlet, Claude; Coulter, Robert; Villa, Irene (Journal article; Peer reviewed, 2020)
      Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method ...
    • Construction of the circle in UniMath 

      Bezem, Marc; Buchholtz, Ulrik; Grayson, Daniel R.; Shulman, Michael (Journal article; Peer reviewed, 2021)
      We show that the type TZ of Z-torsors has the dependent universal property of the circle, which characterizes it up to a unique homotopy equivalence. The construction uses Voevodsky’s Univalence Axiom and propositional ...