umu.sePublikationer
Ändra sökning
Avgränsa sökresultatet
123 101 - 132 av 132
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 101. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    F-Factors in Hypergraphs Via Absorption2015Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 31, nr 3, s. 679-712Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Given integers n ≥ k > l ≥ 1 and a k-graph F with |V(F)| divisible by n, define t k l (n, F) to be the smallest integer d such that every k-graph H of order n with minimum l-degree δl(H) ≥ d contains an F-factor. A classical theorem of Hajnal and Szemerédi in (Proof of a Conjecture of P. Erd˝os, pp. 601–623, 1969) implies that t2 1 (n, Kt) = (1 − 1/t)n for integers t. For k ≥ 3, t k k−1(n, Kk k ) (the δk−1(H) threshold for perfect matchings) has been determined by Kühn and Osthus in (J Graph Theory 51(4):269–280, 2006) (asymptotically) and Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) (exactly) for large n. In this paper, we generalise the absorption technique of Rödl et al. in (J Combin Theory Ser A 116(3):613–636, 2009) to F-factors. We determine the asymptotic values of t k 1 (n, Kk k (m)) for k = 3, 4 and m ≥ 1. In addition, we show that for t > k = 3 and γ > 0, t3 2 (n, K3 t ) ≤ (1− 2 t2−3t+4 +γ )n provided n is large and t|n. We also bound t 3 2 (n, K3 t )from below. In particular, we deduce that t 3 2 (n, K3 4 ) = (3/4+o(1))n answering a question of Pikhurko in (Graphs Combin 24(4):391–404, 2008). In addition, we prove that t k k−1(n, Kk t ) ≤ (1 − t−1 k−1 −1 + γ )n for γ > 0, k ≥ 6 and t ≥ (3 + √ 5)k/2 provided n is large and t|n.

  • 102. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    l-Degree Turan Density2014Ingår i: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 28, nr 3, s. 1214-1225Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let H-n be a k-graph on n vertices. For 0 <= l < k and an l-subset T of V (H-n), define the degree deg(T) of T to be the number of (k - l)-subsets S such that S boolean OR T is an edge in H-n. Let the minimum l-degree of H-n be delta(l) (H-n) = min{deg(T) : T subset of V (H-n) and vertical bar T vertical bar = l}. Given a family F of k-graphs, the l-degree Turan number ex(l) (n, F) is the largest delta(l) (H-n) over all F-free k-graphs H-n on n vertices. Hence, ex(0) (n, F) is the Turan number. We define l-degree Turan density to be pi(kappa)(l) (F) = lim sup(n ->infinity) ex(l)(n, F)/kappa(n-l). In this paper, we show that for k > l > 1, the set of pi(kappa)(l) (F) is dense in the interval [0, 1). Hence, there is no "jump" for l-degree Turan density when k > l > 1. We also give a lower bound on pi(kappa)(l) (F) in terms of an ordinary Turan density.

  • 103. Lo, Allan
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Minimum codegree threshold for (K-4(3)-e)-factors2013Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 120, nr 3, s. 708-721Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Given hypergraphs H and F, an F-factor in H is a spanning subgraph consisting of vertex-disjoint copies of F. Let K-4(3) - e denote the 3-uniform hypergraph on 4 vertices with 3 edges. We Show that for any gamma > 0 there exists an integer n(0) such that every 3-uniform hypergraph H of order n > n(0) with minimum codegree at least (1/2 + gamma)n and 4 vertical bar n contains a (K-4(3) - e)-factor. Moreover, this bound is asymptotically the best possible and we further give a conjecture on the exact value of the threshold for the existence of a (K-4(3) - e)-factor. Thereby, all minimum codegree thresholds for the existence of F-factors are known asymptotically for 3-uniform hypergraphs F on 4 vertices. (C) 2012 Elsevier Inc. All rights reserved.

  • 104.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Perfect matchings in 3-partite 3-uniform hypergraphs2014Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 127, s. 22-57Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let H be a 3-partite 3-uniform hypergraph, i.e. a 3-uniform hypergraph such that every edge intersects every partition class in exactly one vertex, with each partition class of size n. We determine a Dirac-type vertex degree threshold for perfect matchings in 3-partite 3-uniform hypergraphs.

  • 105. Lundow, P. H.
    et al.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials2006Ingår i: Experimental Mathematics, ISSN 1058-6458, E-ISSN 1944-950X, Vol. 15, nr 3, s. 343-353Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    This paper concerns the coefficients of the chromatic polynomial of a graph. We first report on a computational verification of the strict log-concavity conjecture for chromatic polynomials for all graphs on at most 11 vertices, as well as for certain cubic graphs. In the second part of the paper we give a number of conjectures and theorems regarding the behavior of the coefficients of the chromatic polynomial, in part motivated by our computations. Here our focus is on epsilon(G), the average size of a broken-cycle-free subgraph of the graph G, whose behavior under edge deletion and contraction is studied.

  • 106. Lundow, P. H.
    et al.
    Rosengren, A.
    On the p, q-binomial distribution and the Ising model2010Ingår i: PHILOSOPHICAL MAGAZINE, Vol. 90, nr 24, s. 3313-3353, artikel-id PII 923766914Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We employ p, q-binomial coefficients, a generalisation of the binomial coefficients, to describe the magnetisation distributions of the Ising model. For the complete graph this distribution corresponds exactly to the limit case p = q. We apply our investigation to the simple d-dimensional lattices for d = 1, 2, 3, 4, 5 and fit p, q-binomial distributions to our data, some of which are exact but most are sampled. For d = 1 and d = 5, the magnetisation distributions are remarkably well-fitted by p,q-binomial distributions. For d = 4 we are only slightly less successful, while for d = 2, 3 we see some deviations (with exceptions!) between the p, q-binomial and the Ising distribution. However, at certain temperatures near Tc the statistical moments of the fitted distribution agree with the moments of the sampled data within the precision of sampling. We begin the paper by giving results of the behaviour of the p, q-distribution and its moment growth exponents given a certain parameterisation of p, q. Since the moment exponents are known for the Ising model (or at least approximately for d = 3) we can predict how p, q should behave and compare this to our measured p, q. The results speak in favour of the p, q-binomial distribution's correctness regarding its general behaviour in comparison to the Ising model. The full extent to which they correctly model the Ising distribution, however, is not settled.

  • 107. Lundow, Per Håkan
    et al.
    Rosengren, Anders
    The p,q-binomial distribution applied to the 5d Ising model2013Ingår i: PHILOSOPHICAL MAGAZINE, Vol. 93, nr 14, s. 1755-1770Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The leading order form of the magnetization distribution is well-known for the 5d Ising model close to . Its corrections-to-scaling are not known though. Since we have earlier established that this distribution is extremely well-fitted by a -binomial distribution, we report considerably longer series expansions for its moments in terms of three parameters, providing new details on the scaling behaviour of the Ising distribution and its moments near . As applications, we give for example the scaling formulas for the ratios , and the full distribution at .

  • 108.
    Lundow, Per-Håkan
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Matematiska institutionen.
    Compression of transfer matrices2001Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 231, nr 1-3, s. 321-329Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We present a method for reducing the size of transfer matrices by exploiting symmetry. For example, the transfer matrix for enumeration of matchings in the graph C-4 x C-4 x P-n can be reduced from order 65536 to 402 simply due to the 384 automorphisms of C-4 x C-4. The matrix for enumeration of perfect matchings can be still further reduced to order 93, all in a straightforward and mechanical way. As an application we report an improved upper bound for the three-dimensional dimer problem. (C) 2001 Elsevier Science B.V. All rights reserved.

  • 109.
    Lundow, Per-Håkan
    et al.
    KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms2008Ingår i: LMS Journal of Computation and Mathematics, ISSN 1461-1570, E-ISSN 1461-1570, Vol. 11, s. 1-14Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.

  • 110.
    Lönnman, Magnus
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Eulerska grafer: egenskaper och tillämpningar2012Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Denna uppsats handlar om de så kallade eulerska graferna och grafer nära besläktade med dessa. En eulersk graf är en graf där det går att traversera alla kanter i grafen så att varje kant förekommer exakt en gång i traverseringen. Den struktur dessa grafer har uppfyller de villkor Euler ställde upp 1735 då han studerade det klassiska problemet med de sju broarna i Königsberg. Både teoretiska aspekter, som cykeldekomposition och kompatibla eulervägar, samt praktiska tillämpningar, som det kinesiska brevbärarproblemet och DNA-sekvensering (där man använder en de Bruijn-graf) behandlas i den här texten. Här redogörs även för kända och mindre kända metoder för enumeration av eulerska och semieulerska grafer. Dessa innefattar enumeration med hjälp av explicita formler, genererande funktioner samt algoritmiskt via generering. Tabeller med antal grafer presenteras för olika varianter av eulerska grafer (märkta, omärkta, planära etc.). Vid omärkt enumeration används endast den algoritmiska metoden, vilken också har använts för att generera och visa alla eulerska och semieulerska grafer med sju kanter, både enkla grafer och multigrafer.

  • 111.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Complete minors in cubic graphs with few short cycles and random cubic graphs2004Ingår i: Ars combinatoria, ISSN 0381-7032, Vol. 70, s. 289-295Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We first prove that for any fixed kappa a cubic graph with few short cycles contains a K-kappa-minor. This is a direct generalisation of a result on girth by Thomassen. We then use this theorem to show that for any fixed k a random cubic graph contains a Kk-minor asymptotically almost surely.

  • 112.
    Markström, Klas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Even cycle decompositions of 4-regular graphs and line graphs2012Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, nr 17, s. 2676-2681Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    An even cycle decomposition of a graph is a partition of its edge into even cycles. We first give some results on the existence of even cycle decomposition in general 4-regular graphs, showing that K 5 is not the only graph in this class without such a decomposition. Motivated by connections to the cycle double cover conjecture we go on to consider even cycle decompositions of line graphs of 2-connected cubic graphs. We conjecture that in this class even cycle decompositions always exists and prove the conjecture for cubic graphs with oddness at most 2. We also discuss even cycle double covers of cubic graphs.

  • 113.
    Markström, Klas
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Rucinski, Andrzej
    Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees2011Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 32, nr 5, s. 677-687Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We establish a new lower bound on the l-wise collective minimum degree which guarantees the existence of a perfect matching in a k-uniform hypergraph, where 1 <= l < k/2. For l = 1, this improves a long-standing bound of Daykin and Haggkvist (1981) [5]. Our proof is a modification of the approach of Han et al. (2009) from [12]. In addition, we fill a gap left by the results solving a similar question for the existence of Hamilton cycles. (C) 2011 Published by Elsevier Ltd

  • 114.
    Markström, Klas
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Thomason, Andrew
    Wagner, Peter
    Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree2011Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 27, nr 2, s. 243-249Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The smallest n such that every colouring of the edges of K (n) must contain a monochromatic star K (1,s+1) or a properly edge-coloured K (t) is denoted by f (s, t). Its existence is guaranteed by the ErdAs-Rado Canonical Ramsey theorem and its value for large t was discussed by Alon, Jiang, Miller and Pritikin (Random Struct. Algorithms 23:409-433, 2003). In this note we primarily consider small values of t. We give the exact value of f (s, 3) for all s a parts per thousand yen 1 and the exact value of f (2, 4), as well as reducing the known upper bounds for f (s, 4) and f (s, t) in general.

  • 115.
    Markström, Klas
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Unavoidable arrays2010Ingår i: Contributions to Discrete Mathematics, ISSN 1715-0868, E-ISSN 1715-0868, Vol. 5, nr 1, s. 90-106Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    An n x n array is avoidable if for each set of n symbols there is a Latin square on these symbols which diers from the array in every cell. We characterise all unavoidable square arrays with at most 2 symbols, and all unavoidable arrays of order at most 4. We also identify a number of general families of unavoidable arrays, which we conjecture to be a complete account of unavoidable arrays. Next, we investigate arrays with multiple entries in each cell, and identify a number of families of unavoidable multiple entry arrays. We also discuss fractional Latin squares, and their connections to unavoidable arrays.

    We note that when rephrasing our results as edge list-colourings of complete bipartite graphs, we have a situation where the lists of available colours are shorter than the length guaranteed by Galvin's Theorem to allow proper colourings.

  • 116.
    Nilson, Tomas
    et al.
    Mittuniversitetet.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Triple arrays and Youden squares2015Ingår i: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 75, nr 3, s. 429-451Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    This paper addresses the question of when triple arrays can be constructed from Youden squares by removing a column together with the symbols therein, and then exchanging the role of columns and symbols. The scope of the investigation is limited to the standard case of triple arrays with $v=r+c-1$. For triple arrays with $\lambda_{cc}=1$ it is proven that they can never be     constructed in this way, and for triple arrays with $\lambda_{cc}=2$ it is proven that there always exists a suitable Youden square and a suitable column for this construction. Further, it is proven that Youden square constructed from a certain family of difference sets never give rise to triple arrays in this way but always gives rise to double arrays. Finally, it is proven that all triple arrays in the single known infinite family, the Paley triple arrays, can all be constructed in this way for some suitable choice of Youden square and column.

  • 117.
    Olsson, Christoffer
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Discreet Discrete Mathematics: Secret Communication Using Latin Squares and Quasigroups2017Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Denna uppsats beskriver kryptosystem och metoder för hemlighetsdelning baserade på latinska kvadrater och det närliggande konceptet kvasigrupper. Olika sorters chiffer, både symmetriska och asymmetriska, behandlas. Dessutom finns ett kapitel tillägnat kryptografiska hashfunktioner och ett tillägnat metoder för hemlighetsdelning. Huvudsyftet är att beskriva redan existerande metoder för hemlig kommunikation på ett mer lättillgängligt sätt och med nya exempel, men dessutom återskapas ett, till synes, förlorat bevis relaterat till rad-latinska kvadrater samt beskrivs två nya chiffer baserade på isotopa latinska kvadrater.

  • 118.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    On avoiding and completing colorings2019Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    All of my papers are related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend φ to a proper edge coloring of G which avoids L? 

    In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most d-1 edges. In Paper III, G is a (d,s)-edge colorable graph; that is G has a proper d-edge coloring, where every edge is contained in at least s-1 2-colored 4-cycles, L must satisfy certain sparsity conditions and we do not have a partial proper edge precoloring φ on edges of G. The problem in Paper III is also considered in Paper IV and Paper V, but here G can be seen as the complete 3-uniform 3-partite hypergraph K3n,n,n, where n is a power of two in paper IV and n is an even number in paper V.

  • 119.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    On avoiding and completing edge colorings2018Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    These papers are all related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend the precoloring to a proper edge coloring avoiding any list assignment? In the first paper, G is a d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and every list assignment L must satisfy certain sparsity conditions. The second paper still deals with d-dimensional hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most (d - 1) edges. For the third paper, G can be seen as a complete 3-uniform 3-partite hypergraph, every list assignment L must satisfy certain sparsity conditions but we do not have a partial proper edge precoloring φ on edges of G. 

  • 120.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    On restricted colorings of (d,s)-edge colorable graphsManuskript (preprint) (Övrigt vetenskapligt)
    Abstract [en]

    A cycle is 2-colored if its edges are properly colored by two distinct colors. A (d,s)-edge colorable graph G is a d-regular graph that admits a proper d-edge coloring in which every edge of G is in at least s−1 2-colored 4-cycles. Given a (d,s)-edge colorable graph G and a list assigment L of forbidden colors for the edges of G satisfying certain sparsity conditions, we prove that there is a proper d-edge coloring of Gthat avoids L, that is, a proper edge coloring φ of G such that φ(e)∉L(e) for every edge e of G.

  • 121.
    Richter, Dirk
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Goldengorin, Boris
    Faculty of Economic Sciences, University of Groningen, The Netherlands, University of Economics and Business, Lviv Highway 51/2, 29016 Khmelnitsky, Ukraine and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    Department of Computer Science, Washington University, USA.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP2007Ingår i: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007) / [ed] J. Janssen and P. Pralat, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2007, s. 99-111Konferensbidrag (Refereegranskat)
    Abstract [en]

    Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.

  • 122. Riener, Cordian
    et al.
    Theobald, Thorsten
    Jansson Andren, Lina
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Lasserre, Jean B.
    Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization2013Ingår i: Mathematics of Operations Research, ISSN 0364-765X, E-ISSN 1526-5471, Vol. 38, nr 1, s. 122-141Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semidefinite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited, and also propose some methods to efficiently compute the geometric quotient.

  • 123.
    Shcherbak, Denys
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Enumerative approaches and structural results for selected combinatorial problems2019Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
  • 124.
    Shcherbak, Denys
    et al.
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Jäger, Gerold
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The Zero Forcing Number of Bijection Graphs2015Ingår i: Proceedings of 26th International Workshop om Combinatorial Algorithms (IWOCA 2015), Berlin-Heidelberg: Springer, 2015, Vol. 9538, s. 334-345Konferensbidrag (Refereegranskat)
    Abstract [en]

    The zero forcing number of a graph is a graph parameter based on a color change process, which starts with a state, where all vertices are colored either black or white. In the next step a white vertex turns black, if it is the only white neighbor of some black vertex, and this step is then iterated. The zero forcing number Z(G) is defined as the minimum cardinality of a set S of black vertices such that the whole vertex set turns black.

    In this paper we study Z(G) for the class of bijection graphs, where a bijection graph is a graph on 2n vertices that can be partitioned into two parts with n vertices each, joined by a perfect matching. For this class of graphs we show an upper bound for the zero forcing number and classify the graphs that attain this bound. We improve the general lower bound for the zero forcing number, which is Z(G)&#x2265;&#x03B4;(G)" role="presentation" style="box-sizing: border-box; display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">Z(G)≥δ(G)Z(G)≥δ(G), for certain bijection graphs and use this improved bound to find the exact value of the zero forcing number for these graphs. This extends and strengthens results of Yi (2012) about the more restricted class of so called permutation graphs.

  • 125.
    Sjöström, Tomas
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för fysik.
    Discrete time variational mechanics of multidomain systems: Applications to coupled electronic, hydraulic, and multibody systems2012Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    Idag finns det få simulatorer för icke-släta multidomän kretsar som bygger på tidsdiskretisering av Lagranges ekvationer.

    Huvudmålet är att visa att det är möjligt att använda en semi-implicit, parameter fri icke-slät diskret lösare för att simulera kretsar med tidssteg proportionella mot systemens tidsskalor.

    Detta visas genom att implementera olika typer av elektriska, mekaniska och hydrauliska komponenter samt att visa att komponenterna är stabila och har rätt beteende när systemet simuleras av en modifierad block pivot lösare.

    Simulerings resultaten visar att icke-släta Newton metoder med styckvis-linjära komponenter och komplementära villkor är tillräkligt för att simulera brytande komponponenter i de simulerande kretsarna.

  • 126. Trotignon, Nicolas
    et al.
    Pham, Lan Anh
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    chi-bounds, operations, and chords2018Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, nr 2, s. 312-336Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an O(n4m) time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most O(3) colors, where is the maximum number of pairwise adjacent vertices in G.

  • 127.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    A Note on Completing Partial Latin Squares2009Ingår i: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 45, s. 117-124Artikel i tidskrift (Refereegranskat)
  • 128.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Latin Squares with Prescriptions and Restrictions2011Ingår i: The Australasian Journal of Combinatorics, ISSN 1034-4942, Vol. 51, s. 77-87Artikel i tidskrift (Refereegranskat)
  • 129.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Matematiska institutionen.
    List colorings of graphs: a short survey2000Självständigt arbete på avancerad nivå (magisterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
    Abstract [en]

    We present an overview of the current state of the List Chromatic Conjecture (LCC) and results on the choice number of planar graphs, as well as of general progress on the subject of list colorings.

  • 130.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    Partial latin squares are avoidable2011Ingår i: Annals of Combinatorics, ISSN 0218-0006, E-ISSN 0219-3094, Vol. 15, nr 3, s. 485-497Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A square array is avoidable if for each set of n symbols there is an n x n Latin square on these symbols which differs from the array in every cell. The main result of this paper is that for m >= 2 any partial Latin square of order 4m - 1 is avoidable, thus concluding the proof that any partial Latin square of order at least 4 is avoidable.

  • 131.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The intricacy of avoiding arrays2005Manuskript (preprint) (Övrigt vetenskapligt)
  • 132.
    Öhman, Lars-Daniel
    Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
    The intricacy of avoiding arrays is 22006Ingår i: Discrete Mathematics, ISSN 0012-365X, Vol. 306, s. 531-532Artikel i tidskrift (Refereegranskat)
123 101 - 132 av 132
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf