Please wait ... |

Link to record
https://umu.diva-portal.org/smash/person.jsf?pid=authority-person:62509 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt142_recordDirectLink",{id:"formSmash:upper:j_idt142:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt142_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt142_j_idt144",{id:"formSmash:upper:j_idt142:j_idt144",widgetVar:"widget_formSmash_upper_j_idt142_j_idt144",target:"formSmash:upper:j_idt142:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Jäger, Gerold

Open this publication in new window or tab >>Enumeration of sets of mutually orthogonal latin rectangles### Jäger, Gerold

### Öhman, Lars-Daniel

### Markström, Klas

### Shcherbak, Denys

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_some",{id:"formSmash:j_idt204:0:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_otherAuthors",{id:"formSmash:j_idt204:0:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_otherAuthors",multiple:true}); 2024 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 31, no 1, article id #P1.53Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Australian National University Press, 2024
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-222588 (URN)10.37236/9049 (DOI)001183448100001 ()2-s2.0-85187699389 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt379",{id:"formSmash:j_idt204:0:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt385",{id:"formSmash:j_idt204:0:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt391",{id:"formSmash:j_idt204:0:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt391",multiple:true});
#####

##### Funder

eSSENCE - An eScience CollaborationSwedish Research Council, 2014-4897
Available from: 2024-04-08 Created: 2024-04-08 Last updated: 2024-04-08Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

We study sets of mutually orthogonal Latin rectangles (MOLR), and a natural variation of the concept of self-orthogonal Latin squares which is applicable on larger sets of mutually orthogonal Latin squares and MOLR, namely that each Latin rectangle in a set of MOLR is isotopic to each other rectangle in the set. We call such a set of MOLR co-isotopic. In the course of doing this, we perform a complete enumeration of sets of t mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7, for all t < n up to isotopism, and up to paratopism. Additionally, for larger n we enumerate co-isotopic sets of MOLR, as well as sets of MOLR where the autotopism group acts transitively on the rectangles, and we call such sets of MOLR transitive. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are co-isotopic and/or transitive in each step of the construction process. We use the prefix stepwise to refer to sets of MOLR with this property at each step of their construction. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular hypergraphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.

Open this publication in new window or tab >>Optimal strategies for the static black-peg AB game with two and three pegs### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Drewes, Frank

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_some",{id:"formSmash:j_idt204:1:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_otherAuthors",{id:"formSmash:j_idt204:1:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_otherAuthors",multiple:true}); 2024 (English)In: Discrete Mathematics, Algorithms and Applications (DMAA), ISSN 1793-8309, E-ISSN 1793-8317, Vol. 16, no 4, article id 2350049Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

World Scientific, 2024
##### Keywords

Game theory, mastermind, AB game, optimal strategy
##### National Category

Discrete Mathematics
##### Research subject

Mathematics
##### Identifiers

urn:nbn:se:umu:diva-210346 (URN)10.1142/s1793830923500490 (DOI)001034748600002 ()2-s2.0-85165934499 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt379",{id:"formSmash:j_idt204:1:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt385",{id:"formSmash:j_idt204:1:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt391",{id:"formSmash:j_idt204:1:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt391",multiple:true});
#####

##### Funder

The Kempe Foundations, JCK-2022.1
Available from: 2023-06-20 Created: 2023-06-20 Last updated: 2024-06-26Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Computing Science.

The AB Game is a game similar to the popular game Mastermind. We study a version of this game called Static Black-Peg AB Game. It is played by two players, the codemaker and the codebreaker. The codemaker creates a so-called secret by placing a color from a set of c colors on each of p ≤ c pegs, subject to the condition that every color is used at most once. The codebreaker tries to determine the secret by asking questions, where all questions are given at once and each question is a possible secret. As an answer the codemaker reveals the number of correctly placed colors for each of the questions. After that, the codebreaker only has one more try to determine the secret and thus to win the game.

For given p and c, our goal is to find the smallest number k of questions the codebreaker needs to win, regardless of the secret, and the corresponding list of questions, called a (k + 1)-strategy. We present a (⌈4c/3⌉ − 1)-strategy for p = 2 for all c ≥ 2, and a ⌊(3c − 1)/2⌋-strategy for p = 3 for all c ≥ 4 and show the optimality of both strategies, i.e., we prove that no (k + 1)-strategy for a smaller k exists.

Open this publication in new window or tab >>Super domination: graph classes, products and enumeration### Ghanbari, Nima

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Lehtilä, Tuomo

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_some",{id:"formSmash:j_idt204:2:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_otherAuthors",{id:"formSmash:j_idt204:2:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_otherAuthors",multiple:true}); 2024 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 349, p. 8-24Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2024
##### Keywords

Domination number, Hajós sum, Neighbourhood corona product, r-clique sum, Super dominating set
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-221545 (URN)10.1016/j.dam.2024.01.039 (DOI)2-s2.0-85185397337 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt379",{id:"formSmash:j_idt204:2:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt385",{id:"formSmash:j_idt204:2:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt391",{id:"formSmash:j_idt204:2:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt391",multiple:true});
#####

##### Funder

The Research Council of NorwaySwedish Research Council, 2022–04535Academy of Finland, 338797
Available from: 2024-03-13 Created: 2024-03-13 Last updated: 2024-03-13Bibliographically approved

Department of Informatics, University of Bergen, P.O. Box 7803, Bergen, Norway.

Department of Mathematics and Statistics, University of Turku, Turku, Finland.

The dominating set problem (DSP) is one of the most famous problems in combinatorial optimization. It is defined as follows. For a given graph G=(V,E), a dominating set of G is a subset S⊆V such that every vertex in V∖S is adjacent to at least one vertex in S. Furthermore, the DSP is the problem of finding a minimum-size dominating set and the corresponding minimum size, the domination number of G. In this, work we investigate a variant of the DSP, the super dominating set problem (SDSP), which has attracted much attention during the last years. A dominating set S is called a super dominating set of G, if for every vertex u∈S¯=V∖S, there exists a v∈S such that N(v)∩S¯=N(v)∖S={u}. Analogously, the SDSP is to find a minimum-size super dominating set, and the corresponding minimum size, the super domination number of G. The decision variants of both the DSP and the SDSP have been shown to be NP-hard. In this paper, we present tight bounds for the super domination number of the neighbourhood corona product, r-clique sum, and the Hajós sum of two graphs. Additionally, we present infinite families of graphs attaining our bounds. Finally, we give the exact number of minimum size super dominating sets for some graph classes. In particular, the number of super dominating sets for cycles has quite surprising properties as it varies between values of the set [Formula presented] based on nmod4.

Open this publication in new window or tab >>Small youden rectangles, near youden rectangles, and their connections to other row-column designs### Jäger, Gerold

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.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_some",{id:"formSmash:j_idt204:3:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_otherAuthors",{id:"formSmash:j_idt204:3:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_otherAuthors",multiple:true}); 2023 (English)In: Discrete Mathematics & Theoretical Computer Science, ISSN 1462-7264, E-ISSN 1365-8050, Vol. 25, no 1, article id 9Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Centre pour la Communication Scientifique Directe (CCSD), 2023
##### Keywords

block designs, row-column designs, Youden squares
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-206792 (URN)10.46298/DMTCS.6754 (DOI)2-s2.0-85152096973 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt379",{id:"formSmash:j_idt204:3:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt385",{id:"formSmash:j_idt204:3:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt391",{id:"formSmash:j_idt204:3:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt391",multiple:true});
#####

##### Funder

Swedish Research Council, 2014-4897Swedish National Infrastructure for Computing (SNIC)eSSENCE - An eScience Collaboration
Available from: 2023-04-24 Created: 2023-04-24 Last updated: 2023-08-18Bibliographically approved

In this paper we first study k × n Youden rectangles of small orders. We have enumerated all Youden rectangles for a range of small parameter values, excluding the almost square cases where k = n − 1, in a large scale computer search. In particular, we verify the previous counts for (n, k) = (7, 3), (7, 4), and extend this to the cases (11, 5), (11, 6), (13, 4) and (21, 5). For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call near Youden rectangles. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above.

Open this publication in new window or tab >>Assessing the effect of multiple cost changes using reverse set tolerances### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Turkensteen, Marcel

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_some",{id:"formSmash:j_idt204:4:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_otherAuthors",{id:"formSmash:j_idt204:4:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_otherAuthors",multiple:true}); 2022 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771Article in journal (Refereed) In press
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2022
##### Keywords

Combinatorial optimization, Reverse set tolerance, Sensitivity analysis, Tolerance
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-201471 (URN)10.1016/j.dam.2022.10.018 (DOI)2-s2.0-85142695036 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt379",{id:"formSmash:j_idt204:4:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt385",{id:"formSmash:j_idt204:4:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt391",{id:"formSmash:j_idt204:4:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt391",multiple:true});
#####

Available from: 2022-12-06 Created: 2022-12-06 Last updated: 2024-04-26

Department of Economics and Business, School of Business and Social Sciences, University of Aarhus, Aarhus, Denmark.

We determine the sensitivity of a current optimal solution to a combinatorial optimization problem to cost changes in a set of elements. In a recent study, the concept of regular set tolerances has been introduced for a combinatorial optimization problem and for three types of cost functions, namely sum, product, and bottleneck. A regular set tolerance is the supremum amount of cost changes that can be distributed in the most favorable way to multiple elements such as not to change the current optimal solution. In this paper, we introduce an alternative concept, namely the reverse set tolerance, which is a measure of the infimum amount of cost changes to multiple elements such that the current optimal solution becomes non-optimal.

We characterize the specific cases in which reverse set upper and lower tolerances have positive values and in which they are infinite. We also show a criterion for the uniqueness of an optimal solution. Furthermore, we present bounds and exact formulas for reverse set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. We discuss the similarities and differences in the results between regular and reverse set tolerances. Finally, we motivate this new concept by analyzing them for special combinatorial optimization problems with important practical applications.

Open this publication in new window or tab >>Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems### Turkensteen, Marcel

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_some",{id:"formSmash:j_idt204:5:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_otherAuthors",{id:"formSmash:j_idt204:5:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_otherAuthors",multiple:true}); 2022 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 937, p. 1-21Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2022
##### Keywords

Bottleneck objective, Bottleneck Spanning Tree Problem, Combinatorial optimization, Linear Bottleneck Assignment Problem, Sensitivity analysis
##### National Category

Discrete Mathematics Probability Theory and Statistics
##### Identifiers

urn:nbn:se:umu:diva-200411 (URN)10.1016/j.tcs.2022.09.026 (DOI)000894223300001 ()2-s2.0-85139352141 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt379",{id:"formSmash:j_idt204:5:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt385",{id:"formSmash:j_idt204:5:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt391",{id:"formSmash:j_idt204:5:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt391",multiple:true});
#####

Available from: 2022-10-20 Created: 2022-10-20 Last updated: 2023-09-05Bibliographically approved

Department of Economics and Business Economics, School of Business and Social Sciences, Aarhus University, Aarhus, Denmark.

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem.

Open this publication in new window or tab >>Bounds for the Static Permutation Mastermind game### Glazik, Christian

### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Schiemann, Jan

### Srivastav, Anand

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_some",{id:"formSmash:j_idt204:6:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_otherAuthors",{id:"formSmash:j_idt204:6:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_otherAuthors",multiple:true}); 2021 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 344, no 3, article id 112253Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2021
##### Keywords

Static Permutation Mastermind, Game theory, Graph theory, Vertex cover
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-180197 (URN)10.1016/j.disc.2020.112253 (DOI)000608703700004 ()2-s2.0-85098170441 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt379",{id:"formSmash:j_idt204:6:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt385",{id:"formSmash:j_idt204:6:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt391",{id:"formSmash:j_idt204:6:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt391",multiple:true});
#####

Available from: 2021-02-22 Created: 2021-02-22 Last updated: 2021-02-22Bibliographically approved

In this paper' we introduce a variant of Mastermind, which we call Static Permutation Mastermind and which is defined as follows. One player creates a secret code, called secret, consisting of n colors on n pegs, where each color is used exactly once. The second player tries to determine the secret with as few questions as possible, where each question is a possible secret and all questions are asked at once. After having asked all questions, he receives for each question the number of correctly placed colors and has one more try to determine the secret. The main result of this paper is an upper bound of O(n^{1.525}) questions. It is proved by a distinction of pairs of possible secrets with low and high Hamming distance. For pairs with a low Hamming distance we construct questions using certain arithmetic progressions. For pairs with a high Hamming distance we estimate the size of a vertex cover in a suitable hypergraph. With a slight modification of the arguments of Doerr et al. (2016) we also give a lower bound of Ω(nlogn).

Open this publication in new window or tab >>The Metric Dimension of Z(n) x Z(n) x Z(n) is [3n/2]### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Drewes, Frank

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_some",{id:"formSmash:j_idt204:7:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_otherAuthors",{id:"formSmash:j_idt204:7:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_otherAuthors",multiple:true}); 2020 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 806, p. 78p. 344-362Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Elsevier, 2020. p. 78
##### Keywords

weighted tree automaton, N-best analysis, tropical semiring
##### National Category

Computer Sciences Discrete Mathematics
##### Research subject

Computer Science
##### Identifiers

urn:nbn:se:umu:diva-159286 (URN)10.1016/j.tcs.2019.05.042 (DOI)000510523000025 ()2-s2.0-85068555744 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt379",{id:"formSmash:j_idt204:7:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt385",{id:"formSmash:j_idt204:7:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt391",{id:"formSmash:j_idt204:7:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt391",multiple:true});
#####

##### Note

Umeå University, Faculty of Science and Technology, Department of Computing Science.

In this work we determine the metric dimension of Z_{n} × Z_{n} × Z_{n} as ⌊3*n*/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 Z* _{c}^{p}* plus 1 which proves our main result.

Available online 4 July 2019.

Available from: 2019-05-23 Created: 2019-05-23 Last updated: 2023-03-24Bibliographically approvedOpen this publication in new window or tab >>Triples of Orthogonal Latin and Youden Rectangles of small order### Jäger, Gerold

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.PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_some",{id:"formSmash:j_idt204:8:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_otherAuthors",{id:"formSmash:j_idt204:8:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_otherAuthors",multiple:true}); 2019 (English)In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 27, no 4, p. 229-250Article in journal (Refereed) Published
##### Abstract [en]

##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:umu:diva-158857 (URN)10.1002/jcd.21642 (DOI)000459040800001 ()2-s2.0-85059030594 (PubMedID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt379",{id:"formSmash:j_idt204:8:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt385",{id:"formSmash:j_idt204:8:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt391",{id:"formSmash:j_idt204:8:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt391",multiple:true});
#####

Available from: 2019-05-13 Created: 2019-05-13 Last updated: 2024-07-02Bibliographically approved

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.

Open this publication in new window or tab >>An Optimal Strategy for Static Black-Peg Mastermind with Three Pegs### Jäger, Gerold

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.### Drewes, Frank

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_some",{id:"formSmash:j_idt204:9:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_otherAuthors",{id:"formSmash:j_idt204:9:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_otherAuthors",multiple:true}); 2018 (English)In: 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, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2018
##### Series

Lecture Notes in Computer Science
##### Keywords

Mastermind, winning strategy, optimality
##### National Category

Discrete Mathematics Other Computer and Information Science
##### Identifiers

urn:nbn:se:umu:diva-151844 (URN)10.1007/978-3-319-99660-8_25 (DOI)2-s2.0-85053255238 (Scopus ID)
##### Conference

11th International Symposium on Algorithmic Game Theory, Beijing, China, September 11-14, 2018
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt379",{id:"formSmash:j_idt204:9:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt385",{id:"formSmash:j_idt204:9:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt391",{id:"formSmash:j_idt204:9:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt391",multiple:true});
#####

Available from: 2018-09-13 Created: 2018-09-13 Last updated: 2023-03-23Bibliographically approved

Umeå University, Faculty of Science and Technology, Department of Computing Science.

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⌋.