### Browsing by Department "University of Bergen"

Now showing 1 - 7 of 7

###### Results Per Page

###### Sort Options

Item Introduction(2017) Gynnild, Astrid; Nilsson, Maria; Simonsen, Anne Hege; Weselius, Hanna; University of Bergen; Mid Sweden University; Oslo Metropolitan University; Department of MediaItem Parameterized single-exponential time polynomial space algorithm for steiner tree(SIAM PUBLICATIONS, 2019) Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; University of Bergen; Professorship Kaski Petteri; University of California Santa Barbara; Homi Bhabha National Institute; Department of Computer ScienceIn the Steiner Tree problem, we are given as input a connected n-vertex graph with edge weights in \{ 1, 2, . . ., W\} , and a set of k terminal vertices. Our task is to compute a minimum-weight tree that contains all of the terminals. The main result of the paper is an algorithm solving Steiner Tree in time O (7.97 k · n 4 · log W) and using O (n 3 · log nW · log k) space. This is the first single-exponential time, polynomial space FPT algorithm for the weighted Steiner Tree problem. Whereas our main result seeks to optimize the polynomial dependency in n for both the running time and space usage, it is possible to trade between polynomial dependence in n and the single-exponential dependence in k to obtain faster running time as a function of k, but at the cost of increased running time and space usage as a function of n. In particular, we show that there exists a polynomial space algorithm for Steiner Tree running in O (6.751 k n O (1) log W) time. Finally, by pushing such a trade-off between a polynomial in n and an exponential in k dependencies, we show that for any ε > 0 there is an n O (f(ε )) log W space 4 (1+ ε ) k n O (f(ε )) log W time algorithm for Steiner Tree, where f is a computable function depending only on ε .Item Polynomial-Time Approximation of Independent Set Parameterized by Treewidth(Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023-09) Chalermsook, Parinya; Fomin, Fedor; Hamm, Thekla; Korhonen, Tuukka; Nederlof, Jesper; Orgo, Ly; Computer Science Professors; University of Bergen; Utrecht University; Department of Computer Science; Li Gortz, Inge; Farach-Colton, Martin; Puglisi, Simon J.; Herman, GrzegorzWe prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a “non-trivial” approximation ratio (as a function of the number of vertices of the input graph G) can be turned into an approximation algorithm achieving almost the same ratio, albeit as a function of the treewidth of G. More formally, we prove that for any function f, the existence of a polynomial time (n/f(n))-approximation algorithm yields the existence of a polynomial time O(tw · log f(tw)/f(tw))-approximation algorithm, where n and tw denote the number of vertices and the width of a given tree decomposition of the input graph. By pipelining our result with the state-of-the-art O(n · (log log n)2 / log3 n)-approximation algorithm by Feige (2004), this implies an O(tw · (log log tw)3 / log3 tw)-approximation algorithm.Item Solar Cycle Occurrence of Alfvénic Fluctuations and Related Geo-Efficiency(2017) Tanskanen, Eija; Snekvik, K.; Slavin, J. A.; Pérez-Suárez, D.; Viljanen, A.; Goldstein, M. L.; Käpylä, M.J.; Hynönen, Reko; Häkkinen, L. V. T.; Mursula, K.; Department of Electronics and Nanoengineering; University of Bergen; University of Michigan, Ann Arbor; University College London; Finnish Meteorological Institute; Space Science Institute; Department of Computer Science; University of OuluWe examine solar wind intervals with Alfvénic fluctuations (ALFs) in 1995–2011. The annual number, the total annual duration, and the average length of ALFs vary over the solar cycle, having a maximum in 2003 and a minimum in 2009. ALFs are most frequent in the declining phase of solar cycle, when the number of high-speed streams at the Earth's vicinity is increased. There is a rapid transition after the maximum of solar cycle 23 from ALFs being mainly embedded in slow solar wind (<400 km/s) until 2002 to ALFs being dominantly in fast solar wind (>600 km/s) since 2003. Cross helicity increased by 30% from 2002 to 2003 and maximized typically 4–6 h before solar wind speed maximum. Cross helicity remained elevated for several days for highly Alfvénic non-ICME streams, but only for a few hours for ICMEs. The number of substorms increased by about 40% from 2002 to 2003, and the annual number of substorms closely follows the annual cross helicity. This further emphasizes the role of Alfvénic fluctuations in modulating substorm activity. The predictability of substorm frequency and size would be greatly improved by monitoring solar wind Alfvénic fluctuations in addition to the mean values of the important solar wind parameters.Item Tail reconnection in the global magnetospheric context(2017-11-28) Palmroth, Minna; Hoilijoki, Sanni; Juusola, Liisa; Pulkkinen, Tuija I.; Hietala, Heli; Pfau-Kempf, Yann; Ganse, Urs; Von Alfthan, Sebastian; Vainio, Rami; Hesse, Michael; University of Helsinki; Finnish Meteorological Institute; Department of Electronics and Nanoengineering; University of California Los Angeles; CSC - IT Center for Science Ltd.; University of Turku; University of BergenThe key dynamics of the magnetotail have been researched for decades and have been associated with either three-dimensional (3-D) plasma instabilities and/or magnetic reconnection. We apply a global hybrid-Vlasov code, Vlasiator, to simulate reconnection self-consistently in the ion kinetic scales in the noon-midnight meridional plane, including both dayside and nightside reconnection regions within the same simulation box. Our simulation represents a numerical experiment, which turns off the 3-D instabilities but models ion-scale reconnection physically accurately in 2-D. We demonstrate that many known tail dynamics are present in the simulation without a full description of 3-D instabilities or without the detailed description of the electrons. While multiple reconnection sites can coexist in the plasma sheet, one reconnection point can start a global reconfiguration process, in which magnetic field lines become detached and a plasmoid is released. As the simulation run features temporally steady solar windinput, this global reconfiguration is not associated with sudden changes in the solar wind. Further, we show that lobe density variations originating from dayside reconnection may play an important role in stabilising tail reconnection.Item Theatre and language : introduction(2017) Gröndahl, Laura; Watson, Anna; Department of Film; University of BergenItem Triangulations of polygons and stacked simplicial complexes(Springer, 2023-05) Fløystad, Gunnar; Orlich, Milo; University of Bergen; Algebra and Discrete Mathematics; Department of Mathematics and Systems AnalysisA triangulation of a polygon has an associated Stanley–Reisner ideal. We obtain a full algebraic and combinatorial understanding of these ideals and describe their separated models. More generally, we do this for stacked simplicial complexes, in particular for stacked polytopes.