umu.sePublications
Change search
Refine search result
123 51 - 100 of 132
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 51.
    Goldengorin, Boris
    et al.
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Jäger, Gerold
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Tolerances Applied in Combinatorial Optimization2006In: Journal of Computer Science, ISSN 1549-3636, E-ISSN 1552-6607, Vol. 2, no 9, p. 716-734Article in journal (Refereed)
    Abstract [en]

    In this paper we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (Σ,II,MAX) we give some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +∞ or > 0. Analogous results are given for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

  • 52.
    Hägglund, Jonas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On snarks that are far from being 3-edge colorable2016In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 23, no 2, article id P2.6Article in journal (Refereed)
    Abstract [en]

    In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices. Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.

  • 53.
    Hägglund, Jonas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On snarks that are far from being 3-edge colorableManuscript (preprint) (Other academic)
    Abstract [en]

    In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices.     Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.

  • 54.
    Hägglund, Jonas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Snarks: Generation, coverings and colourings2012Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.  

    The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order.

    In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24.

    In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.    

    In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings.

    Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.

  • 55.
    Hägglund, Jonas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On stable cycles and cycle double covers of graphs with large circumference2012In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, p. 2540-2544Article in journal (Refereed)
    Abstract [en]

    A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.

  • 56.
    Hägglund, Jonas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Shortest cycle covers and cycle double covers with large 2-regular subgraphs2013In: Journal of Combinatorics, ISSN 2156-3527, E-ISSN 2150-959X, Vol. 4, no 4, p. 457-468Article in journal (Refereed)
    Abstract [en]

    In this paper, we show that many snarks have a shortest cycle cover of length 4/3 m + c for a constant c, where m is the number of edges in the graph, in agreement with the conjecture that all snarks have shortest cycle covers of length 4/3 m + o(m). In particular, we prove that graphs with perfect matching index at most 4 have cycle covers of length 4/3 m and satisfy the (1,2)-covering conjecture of Zhang, and that graphs with large circumference have cycle covers of length close to 4/3 m. We also prove some results for graphs with low oddness and discuss the connection with Jaeger’s Petersen colouring conjecture.

  • 57.
    Hägglund, Jonas
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Steffen, Eckhard
    Paderborn institute for advanced studies in Computer science and Engineering, Paderborn University.
    Petersen-colorings and some families of snarks2014In: Ars Mathematica Contemporanea, ISSN 1855-3966, Vol. 7, no 1, p. 161-173Article in journal (Other academic)
    Abstract [en]

    In this paper we study Petersen-colorings and strong Petersen-colorings on some well known families of snarks, e.g. Blanusa snarks, Goldberg snarks and flower snarks. In particular, it is shown that flower snarks have a Petersen-coloring but they do not have a strong Petersen-coloring. Furthermore it is proved that possible minimum counterexamples to Jaeger's Petersen-coloring conjecture do not contain a specific subdivision of K-3,K-3.

  • 58.
    Johnson, J. Robert
    et al.
    Queen Mary Univ London, Sch Math Sci, London E1 4NS, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Turán and Ramsey properties of subcube intersection graphs2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, p. 55-70Article in journal (Refereed)
    Abstract [en]

    The discrete cube {0, 1}d is a fundamental combinatorial structure. A subcube of {0, 1}d is a subset of 2k of its points formed by fixing k coordinates and allowing the remaining d - k to vary freely. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no r + 1 of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no k which have non-empty intersection and no l which are pairwise disjoint? These questions are naturally expressed using intersection graphs. The intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. Let I(n, d) be the set of all n vertex graphs which can be represented as the intersection graphs of subcubes in {0, 1}d. With this notation our first question above asks for the largest number of edges in a Kr+1-free graph in I(n, d). As such it is a Turán-type problem. We answer this question asymptotically for some ranges of r and d. More precisely we show that if (k + 1)2 [d/k+1] < n ≥k2[d/k] for some integer k ≥ 2 then the maximum edge density is (1 - 1/k - o(1)) provided that n is not too close to the lower limit of the range. The second question can be thought of as a Ramsey-type problem. The maximum such n can be defined in the same way as the usual Ramsey number but only considering graphs which are in I(n, d). We give bounds for this maximum n mainly concentrating on the case that l is fixed, and make some comparisons with the usual Ramsey number.

  • 59.
    Jäger, Gerold
    Mathematisches Seminar Christian-Albrechts-Universität zu Kiel, Germany.
    A New Algorithm for Computing the Smith Normal Form and its Implementation on Parallel Machines2004In: Proceedings of 6th Workshop on Advances in Parallel and Distributed Computation Models, International Parallel and Distributed Processing Symposium (IPDPS 2004), IEEE Press, 2004Conference paper (Refereed)
    Abstract [en]

    Smith normal form computation is important in many topics, e.g. group theory and number theory. For matrices over the rings Z and F2 [x], we introduce a new Smith normal form algorithm, called Triangular Band Matrix Algorithm, which first computes the Hermite Normalform and then step by step the diagonal form and the Smith normal form. In comparison to the Kannan Bachem Algorithm, which computes the Smith normal form by alternately computing the Hermite normal form and the left Hermite normal form, the theoretical advantage is, that we only once apply the expensive Hermite normal form step. We parallelize the Triangular Band Matrix Algorithm and get a better complexity analysis than for previous parallel algorithms, like the Kannan Bachem Algorithm and the Hartley Hawkes Algorithm. In the part, which is different to the Kannan Bachem Algorithm, the Triangular Band Matrix Algorithm leads to a better efficiency and smaller execution times, even for large example matrices.

  • 60.
    Jäger, Gerold
    University of Essen.
    Algorithmen zur Berechnung der Smith-Normalform und deren Implementation auf Parallelrechnern2001Doctoral thesis, monograph (Other academic)
  • 61.
    Jäger, Gerold
    Computer Science Institute, University of Kiel, Germany.
    An Effective SAT encoding for Magic Labeling2010In: Proceedings of 9th Cologne/Twente workshop on graphs and combinatorial optimization (CTW 2010) / [ed] U. Faigle, R. Schrader, and D. Herrmann, 2010, p. 97-100Conference paper (Refereed)
  • 62.
    Jäger, Gerold
    Department of Computer Science, Washington University, Campus Box 1045, One Brookings Drive, St. Louis, Missouri 63130-4899, USA.
    An Efficient Algorithm for Graph Bisection of Triangularizations2007In: Applied Mathematical Sciences, ISSN 1312-885X, E-ISSN 1314-7552, Vol. 1, no 25, p. 1203-1215Article in journal (Refereed)
    Abstract [en]

    Graph bisection is an elementary problem in graph theory. We consider the best known experimental algorithms and introduce a new algorithm called Longest-Path-Algorithm. Applying this algorithm to the cluster tree generation of hierarchical matrices, arising for example in discretizations of partial equations, we show that this algorithm outperforms previous algorithms.

  • 63.
    Jäger, Gerold
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    An Optimal Strategy for Static Mastermind with Two Pegs2016In: Proceedings of 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Springer Berlin/Heidelberg, 2016, p. 670-682Conference paper (Refereed)
    Abstract [en]

    Mastermind is a famous two-player game which has attracted much attention in literature within the last years. In this work we investigate the static (also called non-adaptive) variant of Mastermind. The principal rule is that the codemaker has to choose a secret consisting of p pegs and c colors for each peg and the codebreaker may give a number of guesses at once, where for each guess he receives information from the codemaker. Using this information he has a final guess for the correct secret. The aim of the game is to minimize the number of guesses. Whereas Goddard has investigated the static version of original Mastermind in 2003, we do such an investigation of its black-peg variant, where the received information consists only of a number of black pegs which corresponds to the number of pegs matching in the corresponding question and the secret. As main result we present a strategy for this game for p=2 pegs and arbitrarily many colors c≥3 colors and prove its feasibility and optimality. Furthermore, by computer search we found optimal strategies for 9 other pairs (pc).

  • 64.
    Jäger, Gerold
    Mathematisches Seminar der Christian-Albrechts-Universität zu Kiel, Germany.
    Parallel Algorithms for Computing the Smith Normal Form of Large Matrices2003In: Proceedings of 10th European PVM/MPI 2003 / [ed] J. Dongarra, D. Laforenza, S. Orlando, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2003, p. 170-179Conference paper (Refereed)
    Abstract [en]

    Smith normal form computation has many applications in group theory, module theory and number theory. As the entries of the matrix and of its corresponding transformation matrices can explode during the computation, it is a very difficult problem to compute the Smith normal form of large dense matrices. The computation has two main problems: the high execution time and the memory requirements, which might exceed the memory of one processor. To avoid these problems, we develop two parallel Smith normal form algorithms using MPI. These are the first algorithms computing the Smith normal form with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel algorithms both have a good efficiency, i.e. by doubling the processes, the execution time is nearly halved, and succeed in computing the Smith normal form of dense example matrices over the rings Z and F2[x] with more than thousand rows and columns.

  • 65.
    Jäger, Gerold
    Mathematisches Seminar, Christian-Albrechts-Universität zu Kiel, Germany.
    Reduction of Smith Normal Form Transformation Matrices2005In: Computing, ISSN 0010-485X, E-ISSN 1436-5057, Vol. 74, no 4, p. 377-388Article in journal (Refereed)
    Abstract [en]

    Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.

  • 66. Jäger, Gerold
    SAT and IP Based Algorithms for Magic Labeling with Applications2013In: Proceedings of 24th International Workshop om Combinatorial Algorithms (IWOCA 2013), Berlin-Heidelberg, 2013, p. 258-268Conference paper (Refereed)
  • 67.
    Jäger, Gerold
    Christian-Albrechts-Universität Kiel.
    The Theory of Tolerances with Applications to the Traveling Salesman Problem2011Other (Refereed)
  • 68.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Arnold, Florian
    SAT and IP Based Algorithms for Magic Labeling Including a Complete Search for Total Magic Labelings2015In: Journal of Discrete Algorithms, ISSN 1570-8667, E-ISSN 1570-8675, Vol. 31, p. 87-103Article in journal (Refereed)
    Abstract [en]

    In this paper a labeling of a graph with n vertices and m   edges is a one-to-one mapping from the union of the set of vertices and edges onto the set {1,2,…,m+n}. Such a labeling is defined as magic, if one or both of the following two conditions is fulfilled: the sum of an edge label and the labels of its endpoint vertices is constant for all edges; the sum of a vertex label and the labels of its incident edges is constant for all vertices. If a graph has a labeling fulfilling both conditions, it is called a totally magic graph. We present effective IP and Sat based algorithms for the problem of finding a magic labeling for a given graph, and we extend these algorithms also to find all magic labelings for a given graph. We experimentally compare the resulted algorithms by applying it to random graphs. Finally, we demonstrate its performance by solving small cases of seven open problems within the theory of magic graphs. As main practical result we perform an exhaustive search showing that no totally magic graph with 11 vertices exists.

  • 69.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs2018In: SAGT: International Symposium on Algorithmic Game Theory: 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings / [ed] Xiaotie Deng, Springer, 2018, Vol. 11059, p. 261-266Conference paper (Refereed)
    Abstract [en]

    Mastermind is a famous game played by a codebreaker against a codemaker. We investigate its static (also called non-adaptive) black-peg variant. Given c colors and p pegs, the codemaker has to choose a secret, a p-tuple of c colors, and the codebreaker asks a set of questions all at once. Like the secret, a question is a p-tuple of c colors. The codemaker then tells the codebreaker how many pegs in each question are correct in position and color. Then the codebreaker has one final question to find the secret. His aim is to use as few of questions as possible. Our main result is an optimal strategy for the codebreaker for p=3 pegs and an arbitrary number c of colors using ⌊3c/2⌋+1questions.

    A reformulation of our result is that the metric dimension of ℤn×ℤn×ℤnis equal to ⌊3n/2⌋.

  • 70.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Drewes, Frank
    Umeå University, Faculty of Science and Technology, Department of Computing Science.
    The Metric Dimension of Zn × Zn × Zn is ⌊3n/2⌋2019In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, , p. 78Article in journal (Refereed)
    Abstract [en]

    In this work we determine the metric dimension of Zn × Zn × Zn as ⌊3n/2⌋ for all n ≥ 2. We prove this result by investigating a variant of Mastermind.

    Mastermind is a famous two-player game that has attracted much attention in the literature in recent years. In particular we consider the static (also called non-adaptive) black-peg variant of Mastermind. The game is played by a codemaker and a codebreaker. Given c colors and p pegs, the principal rule is that the codemaker has to choose a secret by assigning colors to the pegs, i.e., the secret is a p-tuple of colors, and the codebreaker asks a number of questions all at once. Like the secret, a question is a p-tuple of colors chosen from the c available colors. The codemaker then answers all of those questions by telling the codebreaker how many pegs in each question are correctly colored. The goal is to find the minimal number of questions that allows the codebreaker to determine the secret from the received answers. We present such a strategy for this game for p = 3 pegs and an arbitrary number c ≥ 2 of colors using ⌊3c/2⌋ + 1 questions, which we prove to be both feasible and optimal.

    The minimal number of questions required for p pegs and c colors is easily seen to be equal to the metric dimension of Zpc plus 1 which proves our main result.

  • 71.
    Jäger, Gerold
    et al.
    Institute for Computer Science, University of Halle-Wittenberg, Germany.
    Goldengorin, Boris
    Faculty of Economic Sciences, University of Groningen, The Netherlands and Department of Applied Mathematics, Khmelnitsky National University, Ukraine.
    Molitor, Paul
    Institute for Computer Science, University of Halle-Wittenberg, Germany.
    Some Basics on Tolerances2005Report (Refereed)
    Abstract [en]

    In this note we deal with sensitivity analysis of combinatorial optimization problems and its fundamental term, the tolerance. For three classes of objective functions (∑ ∏ MAX) we prove some basic properties on upper and lower tolerances. We show that the upper tolerance of an element is well defined, how to compute the upper tolerance of an element, and give equivalent formulations when the upper tolerance is +1 or > 0. Analogous results are proven for the lower tolerance and some results on the relationship between lower and upper tolerances are given.

  • 72.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Goldengorin, Boris
    Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Unites States.
    Pardalos, Panos M.
    Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, United States.
    The Theory of Set Tolerances2014In: LION 2014: Learning and Intelligent Optimization: Conference Proceedings, 2014, p. 362-377Conference paper (Refereed)
    Abstract [en]

    The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these three types of cost functions we extend this theory from single to set tolerances and the related reverse set tolerances. In particular, we characterize specific values of (reverse) set upper and lower tolerances as positive and infinite, and we present a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present formulas or bounds for computing (reverse) set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. Finally, we give formulas for the minimum and maximum (reverse) set upper and lower tolerances using again their corresponding single tolerance counterparts.

  • 73.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Shcherbak, Denys
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Enumeration of t-tuples of Mutually Orthogonal Latin Rectangles and Finite GeometriesManuscript (preprint) (Other academic)
  • 74.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Shcherbak, Denys
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Triples of Orthogonal Latin and Youden Rectangles of small order2019In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, no 4, p. 229-250Article in journal (Refereed)
    Abstract [en]

    We have performed a complete enumeration of non-isotopic triples of mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7. Here we will present a census of such triples, classified by various properties, including the order of the autotopism group of the triple. As part of this we have also achieved the first enumeration of pairwise orthogonal triples of Youden rectangles. We have also studied orthogonal triples of k×8 rectangles which are formed by extending mutually orthogonal triples with non-trivial autotopisms one row at a time, and requiring that the autotopism group is non-trivial in each step. This class includes a triple coming from the projective plane of order 8. Here we find a remarkably symmetrical pair of triples of 4 × 8 rectangles, formed by juxtaposing two   selected copies of complete sets of MOLS of order 4.

  • 75.
    Jäger, Gerold
    et al.
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Molitor, Paul
    Computer Science Institute, University of Halle-Wittenberg, Germany.
    Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order2008In: Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008) / [ed] B. Yang, D.-Z. Du and C.A. Wang, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2008, p. 211-224Conference paper (Refereed)
    Abstract [en]

    We introduce a new combinatorial optimization problem, which is a generalization of the Traveling Salesman Problem (TSP) and which we call Traveling Salesman Problem of Second Order (2-TSP). It is motivated by an application in bioinformatics, especially the Permuted Variable Length Markov model. We propose seven elementary heuristics and two exact algorithms for the 2-TSP, some of which are generalizations of similar algorithms for the Asymmetric Traveling Salesman Problem (ATSP), some of which are new ideas. Finally we experimentally compare the algorithms for random instances and real instances from bioinformatics. Our experiments show that for the real instances most heuristics lead to optimum or almost-optimum solutions, and for the random instances the exact algorithms need less time than for the real instances.

  • 76.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Peczarski, Marcin
    Bounding memory for Mastermind might not make it harder2015In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 596, p. 55-66Article in journal (Refereed)
  • 77.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, Poland.
    Playing several variants of mastermind with constant-size memory is not harder than with unbounded memory2015In: Combinatorial Algorithms: 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers / [ed] Kratochvíl Jan, Mirka Miller, Dalibor Froncek, Springer Berlin/Heidelberg, 2015, p. 188-199Conference paper (Refereed)
    Abstract [en]

    We investigate a version of the Mastermind game, where the codebreaker may only store a constant number of questions and answers, called Constant-Size Memory Mastermind, which was recently introduced by Doerr and Winzen. We concentrate on the most difficult case, where the codebreaker may store only one question and one answer, called Size-One Memory Mastermind. We consider two variants of the game: the original one, where the answer is coded with white and black pegs, and the simplified one, where only black pegs are used in the answer. We show that for two pegs and an arbitrary number of colors, the number of questions needed by the codebreaker in an optimal strategy in the worst case for these games is equal to the corresponding number of questions in the games without a memory restriction. In other words, for these cases restricting the memory size does not make the game harder for the codebreaker. This is a continuation of a result of Doerr and Winzen, who showed that this holds asymptotically for a fixed number of colors and an arbitrary number of pegs. Furthermore, by computer search we determine additional pairs (p, c), where again the numbers of questions in an optimal strategy in the worst case for Size-One Memory Mastermind and original Mastermind are equal.

  • 78.
    Jäger, Gerold
    et al.
    Institute for Applied Stochastics and Operations Research, Technical University of Clausthal, D-38678 Clausthal, Germany.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
    The number of pessimistic guesses in Generalized Black-peg Mastermind2011In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 111, no 19, p. 933-940Article in journal (Refereed)
    Abstract [en]

    Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible using information he receives from the codemaker after each guess. In Generalized Black-peg Mastermind for given arbitrary numbers p, c, the secret code consists of p pegs each having one of c colors, and the received information consists only of a number of black pegs, where this number equals the number of pegs matching in the corresponding question and the secret code. Let b(p; c) be the pessimistic number of questions for Generalized Black-peg Mastermind. By a computer program we compute several values b(p; c). By introducing some auxiliary games and combining this program with theoretical methods, for arbitrary c we obtain exact formulas for b(2; c), b(3; c) and b(4; c) and give upper and lower bounds for b(5; c) and a lower bound for b(6; c). Furthermore, for arbitrary p, we present upper bounds for b(p; 2), b(p; 3) and b(p; 4). Finally, we give bounds for the general case b(p; c). In particular, we improve an upper bound recently proved by Goodrich.

  • 79.
    Jäger, Gerold
    et al.
    Institute of Computer Science, Martin-Luther University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, ul. Banacha 2, PL-02-097 Warszawa, Poland.
    The number of pessimistic guesses in Generalized Mastermind2009In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 109, no 12, p. 635-641Article in journal (Refereed)
    Abstract [en]

    Mastermind is a famous two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. The code consists of 4 pegs, each of which is one of 6 colors. In Generalized Mastermind a general number p of pegs and a general number c of colors is considered. Let f(p; c) be the pessimistic number of questions for the generalization of Mastermind with an arbitrary number p of pegs and c of colors. By a computer program we compute ten new values of f(p; c). Combining this program with theoretical methods, we compute all values f(3; c) and a tight lower and upper bound for f(4; c). For f(p; 2) we give an upper bound and a lower bound. Finally, combining results for fixed p and c, we give bounds for the general case f(p; c).

  • 80.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Peczarski, Marcin
    Institute of Informatics, University of Warsaw, Poland.
    The worst case number of questions in Generalized AB game with and without white-peg answers2015In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 184, p. 20-31Article in journal (Refereed)
    Abstract [en]

    The AB game is a two-player game, where the codemaker has to choose a secret code and the codebreaker has to guess it in as few questions as possible. It is a variant of the famous Mastermind game, with the only difference that all pegs in both, the secret and the questions must have distinct colors. In this work, we consider the Generalized AB game, where for given arbitrary numbers p, c with p <= c the secret code consists of p pegs each having one of c colors and the answer consists of a number of black and white pegs. There the number of black pegs equals the number of pegs matching in the corresponding question and the secret in position and color, and the number of white pegs equals the additional number of pegs matching in the corresponding question and the secret only in color. We consider also a variant of the Generalized AB game, where the information of white pegs is omitted. This variant is called Generalized Black-peg AB game. Let ab(p, c) and abb(p, c) be the number of questions in the worst case needed by the codebreaker to guess the secret for Generalized AB game and Generalized Black-peg AB game, respectively. Combining a computer program with theoretical considerations, we confirm known exact values of ab(2, c) and ab(3, c) and prove tight bounds for ab(4, c). Furthermore, we present exact values for abb(2, c) and abb(3, c) and tight bounds for abb(4, c)

  • 81.
    Jäger, Gerold
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Shcherbak, Denys
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Öhman, Lars-Daniel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Enumeration of Youden Rectangles of Small ParametersManuscript (preprint) (Other academic)
  • 82.
    Jäger, Gerold
    et al.
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Improved Approximation Algorithms for Maximum Graph Partitioning Problems2005In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 10, no 2, p. 133-167Article in journal (Refereed)
    Abstract [en]

    We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefinite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han, Ye, Zhang (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a ”good” set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a suboptimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.

  • 83.
    Jäger, Gerold
    et al.
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Srivastav, Anand
    Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
    Improved Approximation Algorithms for Maximum Graph Partitioning Problems2004In: Proceedings of 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004) / [ed] P.K. Lodaya and M. Mahajan, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2004, p. 348-359Conference paper (Refereed)
    Abstract [en]

    In this paper we improve the analysis of approximation algorithms based on semidefinite programming for the maximum graph partitioning problems MAX-k-CUT, MAX-k-UNCUT, MAX-k-DIRECTEDCUT, MAX-k-DIRECTED-UNCUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-VERTEX-COVER. It was observed by Han, Ye, Zhang (2002) and Halperin, Zwick (2002) that a parameter-driven random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1994). Halperin and Zwick could describe the approximation factors by a mathematical optimization problem for the above problems for    and found a choice of parameters in a heuristic way. The innovation of this paper is twofold. First, we generalize the algorithm of Halperin and Zwick to cover all cases of k, adding some algorithmic features. The hard work is to show that this leads to a mathematical optimization problem for an optimal choice of parameters. Secondly, as a key-step of this paper we prove that a sub-optimal set of parameters is determined by a linear program. Its optimal solution computed by CPLEX leads to the desired improvements. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained which leaves room for further improvements.

  • 84.
    Jäger, Gerold
    et al.
    Department of Computer Science, Washington University, USA.
    Srivastav, Anand
    Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Germany .
    Wolf, Katja
    Zentrum für Paralleles Rechnen Universität zu Köln, Germany.
    Solving Generalized Maximum Dispersion with Linear Programming2007In: Proceedings of 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007) / [ed] M.-Y. Kao and X.-Y. Li, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2007, p. 1-10Conference paper (Refereed)
    Abstract [en]

    The Generalized Maximum Dispersion problem asks for a partition of a given graph into p vertex-disjoint sets, each of them having at most k vertices. The goal is to maximize the total edge-weight of the induced subgraphs. We present the first LP-based approximation algorithm.

  • 85.
    Jäger, Gerold
    et al.
    Computer Science Institute, University of Halle-Wittenberg, D-06120 Halle (Saale), Germany.
    Wagner, Clemens
    denkwerk, Vogelsanger Straße 66, D-50823 Köln, Germany.
    Efficient parallelizations of Hermite and Smith normal form algorithms2009In: Parallel Computing, ISSN 0167-8191, E-ISSN 1872-7336, Vol. 35, no 6, p. 345-357Article in journal (Refereed)
    Abstract [en]

    Hermite and Smith normal form are important forms of matrices used in linear algebra. These terms have many applications in group theory and number theory. As the entries of the matrix and of its corresponding transformation matrices can explode during the computation, it is a very difficult problem to compute the Hermite and Smith normal form of large dense matrices. The main problems of the computation are the large execution times and the memory requirements which might exceed the memory of one processor. To avoid these problems, we develop parallelizations of Hermite and Smith normal form algorithms. These are the first parallelizations of algorithms for computing the normal forms with corresponding transformation matrices, both over the rings Z and F[x]. We show that our parallel versions have good efficiency, i.e., by doubling the processes, the execution time is nearly halved. Furthermore, they succeed in computing normal forms of dense large example matrices over the rings Q[x], F3[x], and F5[x].

  • 86.
    Jäger, Gerold
    et al.
    Computer Science Institute, Christian-Albrechts-University of Kiel, Germany .
    Zhang, Weixiong
    Department of Computer Science/Department of Genetics, Washington University, United States .
    A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem2010In: Proceedings of 5th International Computer Science Symposium in Russia (CSR 2010) / [ed] F. Ablayev and E.W. Mayr, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2010, p. 216-227Conference paper (Refereed)
    Abstract [en]

    The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, little is known for the HCP in directed graphs (DHCP). The contribution of this work is an e ective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining e ective algorithms for the AP and SAT, our algorithm signicantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.

  • 87.
    Jäger, Gerold
    et al.
    Computer Science Institute, Christian-Albrechts-University of Kiel, D-24118 Kiel, Germany.
    Zhang, Weixiong
    Department of Computer Science and Engineering, Washington University, St. Louis, Missouri 63130, United States.
    An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem2010In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 39, p. 663-687Article in journal (Refereed)
    Abstract [en]

    The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. It is among the first problems used for studying intrinsic properties, including phase transitions, of combinatorial problems. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, a limited amount of work has been done for the HCP in directed graphs (DHCP). The main contribution of this work is an effective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms, including an algorithm based on the award-winning Concorde TSP algorithm. The second result of the current study is an experimental analysis of phase transitions of the DHCP, verifying and refining a known phase transition of the DHCP.

  • 88.
    Khan, Abid
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Three Kotzig graphs form a good frame2015Licentiate thesis, monograph (Other academic)
  • 89.
    Kjelgaard Mikkelsen, Carl Christian
    et al.
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Kågström, Bo
    Umeå University, Faculty of Science and Technology, Department of Computing Science. Umeå University, Faculty of Science and Technology, High Performance Computing Center North (HPC2N).
    Approximate incomplete cyclic reduction for systems which are tridiagonal and strictly diagonally dominant by rows2013In: Applied Parallel and Scientific Computing: 11th International Conference, PARA 2012, Helsinki, Finland, June 10-13, 2012, Revised Selected Papers / [ed] Pekka Manninen and Per Öster, Springer Berlin/Heidelberg, 2013, p. 250-264Conference paper (Refereed)
    Abstract [en]

    Systems which are narrow banded and strictly diagonally dominant by rows can be solved in parallel using a variety of methods including incomplete block cyclic reduction. We show how to accelerate the algorithm by approximating the very first step. We derive tight estimates for the forward error and explain why our procedure is suitable for linear systems obtained by discretizing some common parabolic PDEs. An improved ScaLAPACK style algorithm is presented together with strong scalability results.

  • 90.
    Lantz, Emilott
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    What can Turán tell us about the hypercube?2012Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [en]

    The Turán problem is a fundamental problem in extremal graph theory. It asks what the maximum number of edges a given graph G can have, not containing some forbidden graph H, and is solved using the Turán number ex(n,H), density π(H) and graph Tr(n). Turán's theorem tells us that the Turán graph Tr(n) is the largest Kr+1-free simple graph on n vertices. This paper is an overview of Turán problems for cliques Kn, hypercubes Qn and Hamming graphs H(s,d). We end it by proving a new result we call "the layer theorem", solving the Hamming-Turán problem using a method of creating layers of vertices in a graph. This theorem gives a lower bound for the Hamming-relative Turán density as follows:  where  for the forbidden graph F stretching over t layers and r = χ(F).

  • 91.
    Larsson, Joel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On random cover and matching problems2016Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis consists of the following papers.

    1. I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submitted

    2. II  V. Falgas-Ravry, J. Larsson, K. Markström, Speed and concentration of the covering time for structured coupon collectors, submitted

    3. III  J. Larsson, K. Markström, Biased random k-SAT problems, manuscript

    These papers can all be seen as variations on the same question: Given a large set V and a family F of subsets of V, each assigned a (random) weight, we assign each subfamily G ⊆ F a cost based on the weights of sets that occur in it. What will the minimal cost of a subfamiliy G that covers V be?

    In the first paper, we search for a disjoint cover of the ground set V = {u_1,u_2,...u_n,v_1,v_2,...v_n}, using random 2-sets of the form {u_i, v_j}. In other words, we search for matchings in a bipartite graph. Each edge receives a random weight distributed uniformly in [0, 1], and the cost of a perfect matching using edges with weights l_1,l_2,...l_n is Σ_{i=1}^n l_i^{1/q} for some q > 0.

    The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.

    For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.

  • 92.
    Larsson, Joel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    On random satisfiability and optimization problems2018Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.

    In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.

    Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.

    We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.

  • 93.
    Larsson, Joel
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    The Minimum Perfect Matching in Pseudo-dimension 0<q<1Manuscript (preprint) (Other academic)
    Abstract [en]

    It is known that for Kn,n equipped with i.i.d. exp(1) edge costs, the minimum total cost of a perfect matching converges to π2/6 in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension q≥1, such as Weibull(1,q) costs. In this paper we extend those results all q>0, confirming the Mézard-Parisi conjecture in the last remaining applicable case.

  • 94.
    Larsson, Joel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Biased random k-SATManuscript (preprint) (Other academic)
  • 95.
    Larsson, Joel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Biased random k-SATManuscript (preprint) (Other academic)
    Abstract [en]

    The random k-SAT problem has become one of the most studied intersection points of combinatorics, computer science and physics. The basic problem is as follows: We have a set of n boolean variables and then pick m clauses of size k uniformly at random from the set of all such clauses on our variables (we give a more detailed definition later) and then ask: is the conjunction of these clauses satisfiable?

    We consider a variation of the problem where there is a bias towards variables occuring pure – i.e. variables occur negated w.p. 0<p<1/2 and pure otherwise – and study how the satisfiability threshold depends on p.

    For any fixed k, we find the asymptotics of the threshold as p approaches 0 or 1/2. The former confirms numerical studies.

  • 96.
    Larsson, Joel
    et al.
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Polarized random k-SATManuscript (preprint) (Other academic)
    Abstract [en]

    We introduce a variation of the random k-SAT problem, which we call polarized random k-SAT. In polarized random k-SAT we have a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random k-SAT model.

    Of particular interest is the fully polarized model where p = 0. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated.

    We show that the threshold of satisfiability does not decrease as p moves away from 1. Thus the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for the classical random k-SAT. We also conjecture that the two thresholds coincide.

  • 97. Leader, Imre
    et al.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Uncountable families of vertex-transitive graphs of finite degree2006In: Discrete Mathematics, Vol. 306, no 7, p. 678-679Article in journal (Refereed)
    Abstract [en]

    Recently the following question was relayed to the second author: What is the cardinality of the set of vertex transitive graphs of finite degree? Our aim in this short note is to show that there are $2^{\aleph_{0}}$ such graphs.

  • 98.
    Leino, Anders
    Umeå University, Faculty of Science and Technology, Department of Physics.
    Exact and Monte-Carlo algorithms for combinatorial games2014Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    This thesis concerns combinatorial games and algorithms that can be used to play them.Basic definitions and results about combinatorial games are covered, and an implementation of the minimax algorithm with alpha-beta pruning is presented.Following this, we give a description and implementation of the common UCT (Upper Confidence bounds applied to Trees) variant of MCTS (Monte-Carlo tree search).Then, a framework for testing the behavior of UCT as first player, at various numbers of iterations (namely 2,7, ... 27), versus minimax as second player, is described.Finally, we present the results obtained by applying this framework to the 2.2 million smallest non-trivial positional games having winning sets of size either 2 or 3.It is seen that on almost all different classifications of the games studied, UCT converges quickly to near-perfect play.

  • 99.
    Lindqvist, Lars
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    Övertäckningsdesigner och extremala hypergrafer2012Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
    Abstract [en]

    In this paper we introduce the reader to the fundamentals of coveringdesigns and extremal hypergraph theory. Further, we describe a methodof finding all non-isomorphic extremal hypergraphs EX(n, K^r_s), for givenn, r and s. Lastly, we present the results found by this method and makesome comparisons regarding efficiency between this and the naive method.

  • 100.
    Lo, Allan
    et al.
    Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England.
    Markström, Klas
    Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
    A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs2013In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 1, p. 97-111Article in journal (Refereed)
    Abstract [en]

    A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥(t - 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, . . . , Vt each of size n. We show that, for any γ &gt; 0, if every vertex x ∈ Vi is joined to at least ((t - 1)/t + γ )n vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.

123 51 - 100 of 132
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf