Recent Submissions

  • Minimum Fill-in of Sparse Graphs: Kernelization and Approximation 

    Fomin, Fedor; Geevarghese, Philip; Villanger, Yngve (Dagstuhl Publishing, 2011)
    The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop ...
    Conference object
  • Finding Induced Subgraphs via Minimal Triangulations 

    Fomin, Fedor; Villanger, Yngve (Dagstuhl Publishing, 2010)
    Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems in- cluding Minimum Fill-in and Treewidth. We discover unexpected ...
    Conference object
  • Approximating Acyclicity Parameters of Sparse Hypergraphs 

    Fomin, Fedor; Golovach, Petr; Thilikos, Dimitrios (Dagstuhl Publishing, 2009)
    The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ...
    Conference object
  • Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves 

    Fernau, Henning; Fomin, Fedor; Lokshtanov, Daniel; Raible, Daniel; Saurabh, Saket; Villanger, Yngve (Dagstuhl Publishing, 2009)
    The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint ...
    Conference object
  • Testing the presence of CP violation in the 2HDM 

    Grzadkowski, Bohdan; Øgreid, Odd Magne; Osland, Per (PoS - Proceedings of Science, 2015-04-27)
    We review CP properties of the Two-Higgs-Doublet model. In particular, we show that sponta- neous CP violation occurs in the parameter space on the border between regions allowing explicit CP violation and those where ...
    Conference object
  • Subexponential Algorithms for Partial Cover Problems 

    Fomin, Fedor; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket (Dagstuhl Publishing, 2009)
    Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or ...
    Conference object
  • Impact of springtime Himalayan-Tibetan Plateau snowpack on the onset of the Indian summer monsoon in coupled seasonal forecasts 

    Senan, Retish; Orsolini, Yvan; Weisheimer, Antje; Vitart, Frédéric; Balsamo, Gianpaolo; Dutra, E.; Doblas-Reyes, Franscisco J.; Basang, Droma (Springer, 2016-02-20)
    The springtime snowpack over the Himalayan–Tibetan Plateau (HTP) region and Eurasia has long been suggested to be an influential factor on the onset of the Indian summer monsoon. To assess the impact of realistic initialization ...
    Journal article
  • Finding even subgraphs even faster 

    Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Dagstuhl Publishing, 2015)
    Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on n vertices and a positive integer parameter k, find if there exist k ...
    Conference object
  • Maximum matching width: New characterizations and a fast algorithm for dominating set 

    Jeong, Jisu; Sæther, Sigve Hortemo; Telle, Jan Arne (Dagstuhl Publishing, 2015)
    We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A ...
    Conference object
  • Fast biclustering by dual parameterization 

    Drange, Pål Grønås; Reidl, Felix; Villaamil, Fernando Sánchez; Sikdar, Somnath (Dagstuhl Publishing, 2015)
    We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We show that, in addition to being NP-hard, none ...
    Conference object
  • Parameterized complexity of secluded connectivity problems 

    Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S (Dagstuhl Publishing, 2015)
    The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ...
    Conference object
  • B-chromatic number: Beyond NP-hardness 

    Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket (Dagstuhl Publishing, 2015)
    The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ...
    Conference object
  • Additive Schwarz preconditioner for the finite volume element discretization of symmetric elliptic problems 

    Marcinkowski, Leszek; Rahman, Talal; Loneland, Atle; Valdman, Jan (Springer Netherlands, 2015-09-25)
    A symmetric and a nonsymmetric variant of the additive Schwarz preconditioner are proposed for the solution of a class of finite volume element discretization of the symmetric elliptic problem in two dimensions, with large ...
    Journal article
  • Quick but odd growth of cacti 

    Kolay, Sudeshna; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Dagstuhl Publishing, 2015)
    Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems ...
    Conference object
  • Growth and diel vertical migration patterns of the toxic dinoflagellate Protoceratium reticulatum in a water column with salinity stratification: the role of bioconvection and light 

    Erga, Svein Rune; Olseng, Christine Daae; Aarø, Lars Harald (MEPS, 2015-11-12)
    Novel data on growth and migratory behaviour of a southern Norwegian strain of Protoceratium reticulatum (Dinophyceae) were obtained from long-lasting (14-22 d) experiments in a water column with salinity gradient (ΔS = 4 ...
    Journal article
  • A diagram of wind speed versus air-sea temperature difference to understand the marine atmospheric boundary layer 

    Kettle, Anthony (Elsevier, 2015-08-28)
    This contribution reviews the dynamics in the marine atmospheric boundary layer (MABL) with a diagnostic diagram: wind speed versus air-sea temperature difference or U-ΔT. The diagram was first used by Alfred Woodcock in ...
    Journal article
  • A statistical gap-filling method to interpolate global monthly surface ocean carbon dioxide data 

    Jones, Steve D.; Le Quéré, Corinne; Rödenbeck, Christian; Manning, Andrew C.; Olsen, Are (AGU Publications, 2015-10-24)
    We have developed a statistical gap-filling method adapted to the specific coverage and properties of observed fugacity of surface ocean CO2 (fCO2). We have used this method to interpolate the Surface Ocean CO2 Atlas (SOCAT) ...
    Journal article
  • Meter-scale spark X-ray spectrum statistics 

    Carlson, Brant Edward; Østgaard, Nikolai; Kochkin, Pavlo; Grøndahl, Øystein; Nisi, Ragnhild Schrøder; Weber, Kristian; Scherrer, Zack; LeCaptain, Kristian (AGU Publications, 2015-11-13)
    X-ray emission by sparks implies bremsstrahlung from a population of energetic electrons, but the details of this process remain a mystery. We present detailed statistical analysis of X-ray spectra detected by multiple ...
    Journal article
  • Isavsmelting og postglaciale flaumskredvifter i Arna, Hordaland 

    Skår, Kåre (The University of Bergen, 1975)
    Master thesis
  • The interaction between transpolar arcs and cusp spots 

    Fear, Robert C.; Milan, Steve; Carter, Jenny A.; Maggiolo, Romain (AGU Publications, 2015-11-25)
    Transpolar arcs and cusp spots are both auroral phenomena which occur when the interplanetary magnetic field is northward. Transpolar arcs are associated with magnetic reconnection in the magnetotail, which closes magnetic ...
    Journal article

View more