liu.seSök publikationer i DiVA
Ändra sökning
Avgränsa sökresultatet
12 1 - 50 av 54
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Träffar per sida
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sortering
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
  • Standard (Relevans)
  • Författare A-Ö
  • Författare Ö-A
  • Titel A-Ö
  • Titel Ö-A
  • Publikationstyp A-Ö
  • Publikationstyp Ö-A
  • Äldst först
  • Nyast först
  • Skapad (Äldst först)
  • Skapad (Nyast först)
  • Senast uppdaterad (Äldst först)
  • Senast uppdaterad (Nyast först)
  • Disputationsdatum (tidigaste först)
  • Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
  • 1.
    Arkin, Esther M
    et al.
    Department of Applied Mathematics and Statistics, Stony Brook University, USA .
    Dieckmann, Claudia
    Institute of Computer Science, Freie Universität Berlin, Germany .
    Knauer, Christian
    Institute of Computer Science, Universität Bayreuth, Germany .
    Mitchell, Joseph SB
    Department of Applied Mathematics and Statistics, Stony Brook University, USA .
    Polishchuk, Valentin
    Helsinki Institute for Information Technology, CS Dept, University of Helsinki, Finland .
    Schlipf, Lena
    Institute of Computer Science, Freie Universität Berlin, Germany .
    Yang, Shang
    Department of Computer Science, Stony Brook University, USA .
    Convex transversals2014Ingår i: Computational Geometry, ISSN 0925-7721, Vol. 47, nr 2, s. 224-239Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We answer the question initially posed by Arik Tamir at the Fourth NYU Computational Geometry Day (March, 1987): “Given a collection of compact sets, can one decide in polynomial time whether there exists a convex body whose boundary intersects every set in the collection?”

    We prove that when the sets are segments in the plane, deciding existence of the convex stabber is NP-hard. The problem remains NP-hard if the sets are regular polygons. We also show that in 3D the stabbing problem is hard when the sets are balls. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments in 2D if the vertices of the transversal are restricted to a given set of points. Our algorithm also finds a convex stabber of the maximum number of a set of convex pseudodisks in the plane.

    The stabbing problem is related to “convexity” of point sets measured as the minimum distance by which the points must be shifted in order to arrive in convex position; we give a PTAS to find the minimum shift in 2D, and a 2-approximation in any dimension. We also consider stabbing with vertices of a regular polygon – a problem closely related to approximate symmetry detection.

  • 2.
    Asratian, Armen
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Casselgren, Carl Johan
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten. University of Southern Denmark, Denmark.
    Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results2016Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 82, nr 4, s. 350-373Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 5 be an integer. We show that any proper t-edge coloring of G can be transformed to any proper 4-edge coloring of G using only transformations on 2-colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5-edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. (C) 2015 Wiley Periodicals, Inc.

  • 3.
    Asratian, Armen
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Casselgren, Carl Johan
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Petrosyan, Petros A.
    Yerevan State University, Armenia; National Academic Science, Armenia.
    Some results on cyclic interval edge colorings of graphs2018Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, nr 2, s. 239-252Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A proper edge coloring of a graph G with colors 1,2,,t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree (G)4 admits a cyclic interval (G)-coloring if for every vertex v the degree dG(v) satisfies either dG(v)(G)-2 or dG(v)2. We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for (a,b)-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)-biregular graphs as well as all (2r-2,2r)-biregular (r2) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.

  • 4.
    Ball, Simeon
    et al.
    Universitat Politècnica de Catalunya, Barcelona, Spain.
    Bamberg, John
    The University of Western Australia, Crawley, WA, Australia.
    Devillers, Alice
    The University of Western Australia, Crawley, WA, Australia.
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Spain.
    An alternative way to generalise the pentagon2013Ingår i: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 21, nr 4, s. 163-179Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We introduce the concept of a pentagonal geometry as a generalization of the pentagon and the Desargues configuration, in the same vein that the generalized polygons share the fundamental properties of ordinary polygons. In short, a pentagonal geometry is a regular partial linear space in which for all points x, the points not collinear with the point x, form a line. We compute bounds on their parameters, give some constructions, obtain some nonexistence results for seemingly feasible parameters and suggest a cryptographic application related to identifying codes of partial linear spaces.

  • 5.
    Block, Hans
    Linköpings universitet, Institutionen för datavetenskap. Linköpings universitet, Tekniska högskolan.
    Sport-sort: sorting algorithms and sport tournaments1987Licentiatavhandling, monografi (Övrigt vetenskapligt)
    Abstract [en]

    Arrange a really short, thrilling and fair tournament! Execute parallel sorting in a machine of a new architecture! The author shows how these problems are connected. He designs several new tournament schemes, and analyses them both in theory and in extensive simulations. He uses only elementary mathematical and statistical methods. The results are much better than previous ones, and close to the theoretical limit. Now personal computers can be used to arrange tournaments which give the complete ranking list of several thousands of participants within only 20 - 30 rounds.

  • 6.
    Boyvalenkov, P.
    et al.
    Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, Bulgaria; Faculty of Engineering, South-Western University, Blagoevgrad, Bulgaria.
    Danev, Danyo
    Linköpings universitet, Institutionen för systemteknik, Kommunikationssystem. Linköpings universitet, Tekniska fakulteten.
    Stoyanova, M.
    Faculty of Mathematics and Informatics, Sofia University, Sofia, Bulgaria.
    Refinements of Levenshtein Bounds in q-ary Hamming Spaces2018Ingår i: Problems of Information Transmission, ISSN 0032-9460, E-ISSN 1608-3253, Vol. 54, nr 4, s. 329-342Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We develop refinements of the Levenshtein bound in q-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. We investigate the first relevant cases and present new bounds. In particular, we derive generalizations and q-ary analogs of the MacEliece bound. Furthermore, we provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds.

  • 7.
    Bras-Amorós, Maria
    et al.
    Universitat Rovira i Virgili, Catalonia, Spain.
    Domingo-Ferrer, Josep
    Universitat Rovira i Virgili, Catalonia, Spain.
    Stokes, Klara
    Universitat Rovira i Virgili, Catalonia, Spain.
    Configuraciones combinatóricas y recuperación privada de información por pares2009Konferensbidrag (Övrigt vetenskapligt)
  • 8.
    Bras-Amorós, Maria
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    On the existence of combinatorial configurations2010Ingår i: 3rd International Workshop on Optimal Networks Topologies, 2010, 2010, s. 145-167Konferensbidrag (Övrigt vetenskapligt)
  • 9.
    Bras-Amorós, Maria
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    The semigroup of combinatorial configurations2012Ingår i: Semigroup Forum, ISSN 0037-1912, E-ISSN 1432-2137, Vol. 84, nr 1, s. 91-96Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We elaborate on the existence and construction of the so-called combinatorial configurations. The main result is that for fixed degrees the existence of such configurations is given by a numerical semigroup. The proof is constructive giving a method to obtain combinatorial configurations with parameters large enough.

  • 10.
    Bras-Amorós, Maria
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Greferath, Marcus
    University College Dublin, Ireland.
    Problems related to combinatorial configurations with applications to P2P-user private information retrieval2010Konferensbidrag (Övrigt vetenskapligt)
  • 11.
    Burdakov, Oleg
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Doherty, Patrick
    Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
    Kvarnström, Jonas
    Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Rapport (Övrigt vetenskapligt)
    Abstract [en]

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.   For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed ecient label correcting algorithms.   The presented approach is applied to nding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The eciency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

  • 12.
    Burdakov, Oleg
    et al.
    Linköpings universitet, Matematiska institutionen, Optimeringslära. Linköpings universitet, Tekniska högskolan.
    Doherty, Patrick
    Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
    Kvarnström, Jonas
    Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska högskolan.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Ingår i: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, s. 26-50Konferensbidrag (Refereegranskat)
    Abstract [en]

    We consider the directed Steiner tree problem (DSTP) with a constraint on the total number of arcs (hops) in the tree. This problem is known to be NP-hard, and therefore, only heuristics can be applied in the case of its large-scale instances.For the hop-constrained DSTP, we propose local search strategies aimed at improving any heuristically produced initial Steiner tree. They are based on solving a sequence of hop-constrained shortest path problems for which we have recently developed efficient label correcting algorithms.The presented approach is applied to finding suitable 3D locations where unmanned aerial vehicles (UAVs) can be placed to relay information gathered in multi-target monitoring and surveillance. The efficiency of our algorithms is illustrated by results of numerical experiments involving problem instances with up to 40 000 nodes and up to 20 million arcs.

  • 13.
    Burke, Kyle
    et al.
    Plymouth State University, NH, USA.
    Demaine, Erik D.
    MIT, MA, USA.
    Gregg, Harrison
    Bard Coll Simons Rock, MA, USA.
    Hearn, Robert A.
    Portola Valley, CA USA.
    Hesterberg, Adam
    MIT, MA, USA.
    Hoffmann, Michael
    Swiss Federal Institute Technology, Switzerland.
    Ito, Hiro
    The University of Electro-Communications, Chofu, Japan.
    Kostitsyna, Irina
    University of Iibre Bruxelles, Belgium.
    Leonard, Jody
    Bard Coll Simons Rock, MA, USA.
    Loeffler, Maarten
    University of Utrecht, Netherlands.
    Santiago, Aaron
    Bard Coll Simons Rock, MA, USA.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten. University of Elect Communicat, Japan.
    Uehara, Ryuhei
    Japan Adv Institute Science and Technology, Japan.
    Uno, Yushi
    Osaka Prefecture University, Japan.
    Williams, Aaron
    Bard Coll Simons Rock, MA, USA.
    Single-Player and Two-Player Buttons & Scissors Games2016Ingår i: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 / [ed] Akiyama, J., Ito, H., Sakai, T., Uno, Y., SPRINGER INT PUBLISHING AG , 2016, Vol. 9943, s. 60-72Konferensbidrag (Refereegranskat)
    Abstract [en]

    We study the computational complexity of the Buttons amp; Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C = 2 colors but polytime solvable for C = 1. Similarly the game is NP-complete if every color is used by at most F = 4 buttons but polytime solvable for F amp;lt;= 3. We also consider restrictions on the board size, cut directions, and cut sizes. Finally, we introduce several natural two-player versions of the game and show that they are PSPACE-complete.

  • 14.
    Bäckström, Christer
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Time and Space Bounds for Planning2017Ingår i: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 60, s. 595-638Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    There is an extensive literature on the complexity of planning, but explicit bounds on time and space complexity are very rare. On the other hand, problems like the constraint satisfaction problem (CSP) have been thoroughly analysed in this respect. We provide a number of upper- and lower-bound results (the latter based on various complexity-theoretic assumptions such as the Exponential Time Hypothesis) for both satisficing and optimal planning. We show that many classes of planning instances exhibit a dichotomy: either they can be solved in polynomial time or they cannot be solved in subexponential time and thus require O (2(cn)) time for some c amp;gt; 0. In many cases, we can even prove closely matching upper and lower bounds; for every epsilon amp;gt; 0, the problem can be solved in time O (2((1+epsilon)n)) but not in time O (2((1-epsilon)n)). Our results also indicate, analogously to CSPs, the existence of sharp phase transitions. We finally study and discuss the trade-off between time and space. In particular, we show that depth-first search may sometimes be a viable option for planning under severe space constraints.

  • 15.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Haggkvist, Roland
    Umeå University, Sweden.
    Coloring Complete and Complete Bipartite Graphs from Random Lists2016Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, nr 2, s. 533-542Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

  • 16.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Khachatrian, Hrant H.
    Yerevan State Univ, Armenia.
    Petrosyan, Petros A.
    Yerevan State Univ, Armenia.
    Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs2018Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 341, nr 3, s. 627-637Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    An interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. Denote by w(G) (w(c)(G)) and W(G) (W-c(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G, respectively. We present some new sharp bounds on w(G) and W(G) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2-connected multigraph with an interval coloring, then W(G) amp;lt;= 1 + left perpendicular vertical bar V(G)vertical bar/2 right perpendicular (Delta(G) - 1). We also give several results towards the general conjecture that W-c(G) amp;lt;= I vertical bar V(G)vertical bar for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4. (C) 2017 Elsevier B.V. All rights reserved.

    Publikationen är tillgänglig i fulltext från 2019-11-27 16:26
  • 17.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Markstrom, Klas
    Umea Univ, Sweden.
    Pham, Lan Anh
    Umea Univ, Sweden.
    Latin cubes with forbidden entries2019Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, nr 1, artikel-id P1.2Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant gamma amp;gt; 0 such that if n = 2(t) and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma n times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 amp;lt;= i, j, k amp;lt;= n, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A.

  • 18.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Petrosyan, Petros A.
    Yerevan State University, Armenia.
    Toft, Bjarne
    University of Southern Denmark, Denmark.
    On interval and cyclic interval edge colorings of (3,5)-biregular graphs2017Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 340, nr 11, s. 2678-2687Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A proper edge coloring f of a graph G with colors 1, 2, 3, . . . , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G, the colors on the edges incident to v either form an interval or the set {1, . . . t} \ {f (e) : e is incident to v} is an interval. A bipartite graph G is (a, b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b; it has been conjectured that all such graphs have interval colorings. We prove that every (3, 5)-biregular graph has a cyclic interval coloring and we give several sufficient conditions for a (3, 5)-biregular graph to admit an interval coloring. (C) 2016 Elsevier B.V. All rights reserved.

  • 19.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Sune Pedersen, Anders
    University of Southern Denmark, Denmark; Aarhus University Hospital, Denmark.
    Hadwigers Conjecture for inflations of 3-chromatic graphs2016Ingår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 51, s. 99-108Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Hadwigers Conjecture states that every k-chromatic graph has a complete minor of order k. A graph G is an inflation of a graph G if G is obtained from G by replacing each vertex upsilon of G by a clique C-upsilon and joining two vertices of distinct cliques by an edge if and only if the corresponding vertices of G are adjacent. We present an algorithm for computing an upper bound on the chromatic number chi (G) of any inflation G of any 3-chromatic graph G. As a consequence, we deduce that Hadwigers Conjecture holds for any inflation of any 3-colorable graph. (C) 2015 Elsevier Ltd. All rights reserved.

  • 20.
    Casselgren, Carl Johan
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten. University of Southern Denmark, Denmark.
    Toft, Bjarne
    University of Southern Denmark, Denmark.
    One-sided interval edge-colorings of bipartite graphs2016Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 339, nr 11, s. 2628-2639Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let G be a bipartite graph with bipartition (X, Y). An X-interval coloring of G is a proper edge-coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int)(G, X) the minimum k such that G has an X-interval coloring with k colors. In this paper we give various upper and lower bounds on chi(int)(G, X) in terms of the vertex degrees of G. We also determine chi(int) (G, X) exactly for some classes of bipartite graphs G. Furthermore, we present upper bounds on chi(int) (G, X) for classes of bipartite graphs G with maximum degree Delta(G) at most 9: in particular, if Delta(G) = 4, then chi(int) (G, X) amp;lt;= 6; if Delta(G) = 5, then chi(int) (G, X) amp;lt;= 15; if Delta(G) = 6, then chi(int) (G, X) amp;lt;= 33. (C) 2016 Elsevier B.V. All rights reserved.

  • 21.
    Eriksson, T.
    et al.
    Linköpings universitet, Institutionen för systemteknik. Linköpings universitet, Tekniska högskolan.
    Körner, J.
    Bell Laboratories, Murray Hill, USA / Mathematical Institute of the Hungari an Academy of Sciences, Budapest, Hungary.
    Successive Encoding of Correlated Sources1982Rapport (Övrigt vetenskapligt)
    Abstract [en]

    The encoding of a discrete memoryless multiple source  for reconstruction of a sequence  with  is considered. We require that the encoding should be such that  is encoded first without any consideration of  , while in a seeond part of the encoding this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special case  . Comparisons with the Slepian-Wolf problem [3] and the Ahlswede-Körner-Wyner side information problem [2 ], [9) are carried out.

  • 22.
    Fekete, Sandor P.
    et al.
    TU Braunschweig, Germany.
    Haas, Andreas
    TU Braunschweig, Germany.
    Hemmer, Michael
    TU Braunschweig, Germany.
    Hoffmann, Michael
    Swiss Federal Institute Technology, Switzerland.
    Kostitsyna, Irina
    TU Eindhoven, Netherlands.
    Krupke, Dominik
    TU Braunschweig, Germany.
    Maurer, Florian
    TU Braunschweig, Germany.
    Mitchell, Joseph S. B.
    SUNY Stony Brook, NY 11794 USA.
    Schmidt, Arne
    TU Braunschweig, Germany.
    Schmidt, Christiane
    Linköpings universitet, Institutionen för teknik och naturvetenskap, Kommunikations- och transportsystem. Linköpings universitet, Tekniska fakulteten.
    Troegel, Julian
    TU Braunschweig, Germany.
    Computing Nonsimple Polygons of Minimum Perimeter2016Ingår i: EXPERIMENTAL ALGORITHMS, SEA 2016, SPRINGER INT PUBLISHING AG , 2016, Vol. 9685, s. 134-149Konferensbidrag (Refereegranskat)
    Abstract [en]

    We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.

  • 23.
    Feng, Bin
    et al.
    Information Networking Institute, Carnegie Mellon University, Pittsburgh, 15213, USA.
    Liu, Yang
    School of Electrical and Electronic Engineering, Hubei University of Technology, Wuhan, China.
    An Improved RRT Based Path Planning with Safe Navigation2014Ingår i: Proceedings from the 2013 International Symposium on Vehicle, Mechanical, and Electrical Engineering, ISVMEE 2013, Taiwan, China, 21-22 December, 2014, Vol. 494-495, s. 1080-1083Konferensbidrag (Refereegranskat)
    Abstract [en]

    Path planning has been a crucial problem in robotics research. Some algorithms, such as Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Trees (RRT), have been proposed to tackle this problem. However, these algorithms have their own limitations when applying in a real-world domain, such as RoboCup Small-Size League (SSL) competition. This paper raises a novel improvement to the existing RRT algorithm to make it more applicable in real-world.

  • 24.
    Glasser, Christian
    et al.
    Julius Maximilian University, Germany.
    Jonsson, Peter
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Martin, Barnaby
    University of Durham, England.
    Circuit satisfiability and constraint satisfaction around Skolem Arithmetic2017Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 703, s. 18-36Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glasser et al. [1] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits-involving complement, intersection, union and multiplication-to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [1] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N; x), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete. (C) 2017 Elsevier B.V. All rights reserved.

  • 25.
    Granholm, Jonas
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Local Conditions for Cycles in Graphs2019Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle. The problem of determining if a graph is Hamiltonian has been studied extensively, and there are many known sufficient conditions for Hamiltonicity.

    A large portion of these conditions relate the degrees of vertices of the graph to the number of vertices in the entire graph, and thus they can only apply to a limited set of graphs with high edge density. In a series of papers, Asratian and Khachatryan developed local analogues of some of these criteria. These results do not suffer from the same drawbacks as their global counterparts, and apply to wider classes of graphs.

    In this thesis we study this approach of creating local conditions for Hamiltonicity, and use it to develop local analogues of some classic results. We also study how local criteria can influence other global properties of graphs. Finally, we will see how these local conditions can allow us to extend theorems on Hamiltonicity to infinite graphs.

  • 26.
    Granholm, Jonas
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Some cyclic properties of graphs with local Ore-type conditions2016Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
    Abstract [en]

    A Hamilton cycle in a graph is a cycle that passes through every vertex of the graph. A graph is called Hamiltonian if it contains such a cycle.

    In this thesis we investigate two classes of graphs, defined by local criteria. Graphs in these classes, with a simple set of exceptions K, were proven to be Hamiltonian by Asratian, Broersma, van den Heuvel, and Veldman in 1996 and by Asratian in 2006, respectively.

    We prove here that in addition to being Hamiltonian, graphs in these classes have stronger cyclic properties. In particular, we prove that if a graph G belongs to one of these classes, then for each vertex x in G there is a sequence of cycles such that each cycle contains the vertex x, and

    • the shortest cycle in the sequence has length at most 5;
    • the longest cycle in the sequence is a Hamilton cycle (unless G belongs to the set of exceptions K, in which case the longest cycle in the sequence contains all but one vertex of G);
    • each cycle in the sequence except the first contains all vertices of the previous cycle, and at most two other vertices.

    Furthermore, for each edge e in G that does not lie on a triangle, there is a sequence of cycles with the same three properties, such that each cycle in the sequence contains the edge e.

  • 27.
    Hansson, Mikael
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Generalised Ramsey numbers for two sets of cycles2018Ingår i: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 238, s. 86-94Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Let C-1 and C-2 be two sets of cycles. We determine all generalised Ramsey numbers R(C-1, C-2) such that C-1 or C-2 contains a cycle of length at most 6. This generalises previous results of Erdos, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also provide a complete classification of most (C-1, C-2)-critical graphs such that C-1 or C-2 contains a cycle of length at most 5. For length 4, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which vertical bar C-1 vertical bar = vertical bar C-2 vertical bar = 1. For lengths 3 and 5, our results are new also in this special case. (C) 2017 Elsevier B.V. All rights reserved.

    Publikationen är tillgänglig i fulltext från 2020-01-06 13:08
  • 28.
    Hansson, Mikael
    et al.
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska fakulteten.
    Hultman, Axel
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    A word property for twisted involutions in Coxeter groups2019Ingår i: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 161, s. 220-235Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Given an involutive automorphism theta of a Coxeter system (W, S), let J(theta) subset of W denote the set of twisted involutions. We provide a minimal set of moves that can be added to the braid moves, in order to connect all reduced S-expressions (also known as admissible sequences, reduced I-theta-expressions, or involution words) for any given w is an element of J(theta). This can be viewed as an analogue of the well-known word property for Coxeter groups. It improves upon a result of Hamaker, Marberg, and Pawlowski, and generalises similar statements valid in certain types due to Hu, Zhang, Wu, and Marberg. (C) 2018 Elsevier Inc. All rights reserved.

  • 29.
    Hultman, Axel
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Supersolvability and the Koszul property of root ideal arrangements2016Ingår i: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 144, s. 1401-1413Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    A root ideal arrangement A_I is the set of reflecting hyperplanes corresponding to the roots in an order ideal I of the root poset on the positive roots of a finite crystallographic root system. A characterisation of supersolvable root ideal arrangements is obtained. Namely, A_I is supersolvable if and only if I is chain peelable, meaning that it is possible to reach the empty poset from I by in each step removing a maximal chain which is also an order filter. In particular, supersolvability is preserved under taking subideals. We identify the maximal ideals that correspond to non-supersolvable arrangements. There are essentially two such ideals, one in type D_4 and one in type F_4. By showing that A_I is not line-closed if I contains one of these, we deduce that the Orlik-Solomon algebra OS(A_I) has the Koszul property if and only if A_I is supersolvable.

  • 30.
    Izquierdo, Milagros
    et al.
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Stokes, Klara
    Högskolan i Skövde.
    Isometric Point-Circle Configurations on Surfaces from Uniform Maps2016Ingår i: Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009, Vol. 159, s. 201-212Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    We embed neighborhood geometries of graphs on surfaces as point-circle configurations. We give examples coming from regular maps on surfaces with a maximum number of automorphisms for their genus, and survey geometric realization of pentagonal geometries coming from Moore graphs. An infinite family of point-circle v4'>v4v4 configurations on p-gonal surfaces with two p-gonal morphisms is given. The image of these configurations on the sphere under the two p-gonal morphisms is also described.

  • 31.
    Jonsson, Erik
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik.
    Numerical Range of Square Matrices: A Study in Spectral Theory2019Självständigt arbete på grundnivå (kandidatexamen), 10,5 poäng / 16 hpStudentuppsats (Examensarbete)
    Abstract [en]

    In this thesis, we discuss important results for the numerical range of general square matrices. Especially, we examine analytically the numerical range of complex-valued $2 \times 2$ matrices. Also, we investigate and discuss the Gershgorin region of general square matrices. Lastly, we examine numerically the numerical range and Gershgorin regions for different types of square matrices, both contain the spectrum of the matrix, and compare these regions, using the calculation software Maple. 

  • 32.
    Jonsson, Peter
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
    Thapper, Johan
    Univ Paris Est Marne la Vallee, France.
    Tractability conditions for numeric CSPs2018Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 715, s. 21-34Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    The computational complexity of the constraint satisfaction problem (CSP) with semilinear relations over the reals has gained recent attraction. As a result, its complexity is known for all finite sets of semilinear relations containing the relation R+ = {(x, y, z) is an element of R-3 vertical bar x + y = z}. We consider larger and more expressive classes of relations such as semialgebraic and o-minimal relations. We present a general result for characterising computationally hard fragments and, under certain side conditions, this result implies that polynomial-time solvable fragments are only to be found within two limited families of sets of relations. In the setting of semialgebraic relation, our result takes on a simplified form and we provide a full complexity classification for constraint languages that consist of algebraic varieties. Full classifications like the one obtained here for algebraic varieties or the one for semilinear relations appear to be rare and we discuss several barriers for obtaining further such results. These barriers have strong connections with well-known open problems concerning the complexity of various restrictions of convex programming. (c) 2018 Elsevier B.V. All rights reserved.

  • 33.
    Kamalian, Rafayel
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    On a number of colors in cyclically interval edgecolorings of trees2010Rapport (Övrigt vetenskapligt)
    Abstract [en]

    A proper edge t-coloring of a graph G is a coloring of edges of G with colors 1,2,...,t such that each edge receives one color and no two adjacent edges receive the same color. A proper edge t-coloring of  G is called  a cyclically interval t-coloring if 1) at least one edge is colored k, for each k=1,2,...,t., and 2) for each vertex v of G the colors of edges incident with v are consecutive modulo t.We find, for an arbitrary tree G, all possible values of t  for which G admits a cyclically interval  t-coloring.

  • 34.
    Karlsson, Patrik
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    Diskret krökning, en jämförelse2012Självständigt arbete på grundnivå (kandidatexamen), 10,5 poäng / 16 hpStudentuppsats (Examensarbete)
    Abstract [sv]

    I detta kandidatarbete undersöker och jämför vi två olika metoder för att approximera gauss- och medelkrökningen hos en yta i rummet som är given som en mängd av punkter. Det är viktigt att försöka få en bra analogi mellan diskret krökning och analytisk krökning då man ofta startar med en mängd punkter i de praktiska fallen, som t ex i tillverkningsindustrin, igenkänning av objekt (inscannade bilder) och datorgrafik. Givet dessa punkter och en bra approximation av gauss- och medelkrökningen kan man få mer information om ytans geometri och beteende.

    För att kunna förstå dessa begrepp och metoder/algoritmer så behandlas först den bakomliggande teorin och sedan metoderna.

    Den första metoden är att återge ytan med hjälp av Bézierytor, vilka vi kan utföra geometriska operationer på utan problem och även få fram gauss- och medelkrökningen.

    Den andra metoden kommer från artikeln ``Discrete Differential-Geometry Operators for Triangulated 2-Manifolds'' av Mark Meyer, Mathieu Desbrun, Peter Schröder och Alan H. Barr. Deras approximationer av krökningarna kräver en triangulering av ytan, vilket de inte ger någon algoritm för. De tittar på ett område runt varje punkt och approximerar krökningarna genom detta område, även Gauss-Bonnets sats används för approximering av gausskrökningen.

    Mina simuleringar visar att Bézierytornas approximationer av gauss- och medelkrökningar är konvergenta och att alla värden ligger relativt nära varandra. Artikelns algoritm fungerar bra för gauss- och medelkrökning men deras algoritm beror väldigt mycket på trianguleringen vilket gör att man behöver ha krav på den triangulerade ytan, vilket i sig är ett svårt problem att lösa.

  • 35.
    Kurujyibwami, Celestin
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik. Linköpings universitet, Tekniska fakulteten.
    Admissible transformations and the group classification of Schrödinger equations2017Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
    Abstract [en]

    We study admissible transformations and solve group classification problems for various classes of linear and nonlinear Schrödinger equations with an arbitrary number n of space variables.

    The aim of the thesis is twofold. The first is the construction of the new theory of uniform seminormalized classes of differential equations and its application to solving group classification problems for these classes. Point transformations connecting two equations (source and target) from the class under study may have special properties of semi-normalization. This makes the group classification of that class using the algebraic method more involved. To extend this method we introduce the new notion of uniformly semi-normalized classes. Various types of uniform semi-normalization are studied: with respect to the corresponding equivalence group, with respect to a proper subgroup of the equivalence group as well as the corresponding types of weak uniform semi-normalization. An important kind of uniform semi-normalization is given by classes of homogeneous linear differential equations, which we call uniform semi-normalization with respect to linear superposition of solutions.

    The class of linear Schrödinger equations with complex potentials is of this type and its group classification can be effectively carried out within the framework of the uniform semi-normalization. Computing the equivalence groupoid and the equivalence group of this class, we show that it is uniformly seminormalized with respect to linear superposition of solutions. This allow us to apply the version of the algebraic method for uniformly semi-normalized classes and to reduce the group classification of this class to the classification of appropriate subalgebras of its equivalence algebra. To single out the classification cases, integers that are invariant under equivalence transformations are introduced. The complete group classification of linear Schrödinger equations is carried out for the cases n = 1 and n = 2.

    The second aim is to study group classification problem for classes of generalized nonlinear Schrödinger equations which are not uniformly semi-normalized. We find their equivalence groupoids and their equivalence groups and then conclude whether these classes are normalized or not. The most appealing classes are the class of nonlinear Schrödinger equations with potentials and modular nonlinearities and the class of generalized Schrödinger equations with complex-valued and, in general, coefficients of Laplacian term. Both these classes are not normalized. The first is partitioned into an infinite number of disjoint normalized subclasses of three kinds: logarithmic nonlinearity, power nonlinearity and general modular nonlinearity. The properties of the Lie invariance algebras of equations from each subclass are studied for arbitrary space dimension n, and the complete group classification is carried out for each subclass in dimension (1+2). The second class is successively reduced into subclasses until we reach the subclass of (1+1)-dimensional linear Schrödinger equations with variable mass, which also turns out to be non-normalized. We prove that this class is mapped by a family of point transformations to the class of (1+1)-dimensional linear Schrödinger equations with unique constant mass.

    Delarbeten
    1. Equivalence groupoid for (1+2)-dimensional linear Schrodinger equations with complex potentials
    Öppna denna publikation i ny flik eller fönster >>Equivalence groupoid for (1+2)-dimensional linear Schrodinger equations with complex potentials
    2015 (Engelska)Ingår i: SEVENTH INTERNATIONAL WORKSHOP: GROUP ANALYSIS OF DIFFERENTIAL EQUATIONS AND INTEGRABLE SYSTEMS (GADEISVII), IOP Publishing: Conference Series / Institute of Physics (IoP) , 2015, Vol. 621, nr UNSP 012008, s. UNSP 012008-Konferensbidrag, Publicerat paper (Refereegranskat)
    Abstract [en]

    We describe admissible point transformations in the class of (1+2)-dimensional linear Schrodinger equations with complex potentials. We prove that any point transformation connecting two equations from this class is the composition of a linear superposition transformation of the corresponding initial equation and an equivalence transformation of the class. This shows that the class under study is semi-normalized.

    Ort, förlag, år, upplaga, sidor
    IOP Publishing: Conference Series / Institute of Physics (IoP), 2015
    Serie
    Journal of Physics Conference Series, ISSN 1742-6588 ; 621
    Nationell ämneskategori
    Matematik
    Identifikatorer
    urn:nbn:se:liu:diva-120668 (URN)10.1088/1742-6596/621/1/012008 (DOI)000357939100008 ()
    Konferens
    7th International Workshop on Group Analysis of Differential Equations and Integrable Systems (GADEIS)
    Tillgänglig från: 2015-08-20 Skapad: 2015-08-20 Senast uppdaterad: 2017-05-15
  • 36.
    Lundqvist, Anders
    Linköpings universitet, Institutionen för systemteknik, Datatransmission. Linköpings universitet, Tekniska högskolan.
    Cyclically permutable codes1997Doktorsavhandling, monografi (Övrigt vetenskapligt)
    Abstract [en]

    A cyclically permutable code is a set of codewords having the property that no codeword is a cyclic shift of another codeword. We study the problem of constructing cyclically permutable codes of large size and low correlation.

    Cyclically permutable codes are used in code-division multiple-access systems realized by e.g. direct-sequence modulation or frequency-hopping. Advantages of code-division multiple-access to conventional access methods, such as timedivision and frequency-division, include greater flexibility, better robustness and that no synchronization among the transmitters is needed.

    Among our main results are an efficient method of selecting cyclically distinct codewords from linear cyclic codes, a new family of sequences for direct-sequence modulation, several constructions of hopping-sequences for multiple-access coupled with a decoding algorithm for asynchronous communication.

    We have also constructed new binary constant-weight codes of high minimum distance.

  • 37.
    Ogniewski, Jens
    Linköpings universitet, Institutionen för systemteknik, Informationskodning. Linköpings universitet, Tekniska fakulteten.
    Artifact-Free Color Interpolation2015Ingår i: Proceedings SCCG: 2015 31st Spring Conference on Computer Graphics, ASSOC COMPUTING MACHINERY , 2015, s. 116-119Konferensbidrag (Refereegranskat)
    Abstract [en]

    Color interpolation is still the most used method for image upsampling, since it offers the simplest and therefore fastest algorithms. However, in recent years research concentrated on other techniques to counter the shortcomings of interpolation techniques (like color artifacts or the fact that interpolation does not take statistics into account), while interpolation itself has ceased to be an active research topic. Still, current interpolation techniques can be improved. Especially it should be possible to avoid color artifacts by carefully choosing the correct interpolation schemes. In this paper we derive mathematical constraints which need to be fulfilled to reach an artifact-free interpolation, and use these to develop an interpolation method which is basically a self-configuring cubic spline.

  • 38.
    Rahm, Ludwig
    Linköpings universitet, Matematiska institutionen, Matematik och tillämpad matematik.
    Generating functions and regular languages of walks with modular restrictions in graphs2017Självständigt arbete på grundnivå (kandidatexamen), 10,5 poäng / 16 hpStudentuppsats (Examensarbete)
    Abstract [en]

    This thesis examines the problem of counting and describing walks in graphs, and the problem when such walks have modular restrictions on how many timesit visits each vertex. For the special cases of the path graph, the cycle graph, the grid graph and the cylinder graph, generating functions and regular languages for their walks and walks with modular restrictions are constructed. At the end of the thesis, a theorem is proved that connects the generating function for walks in a graph to the generating function for walks in a covering graph.

  • 39.
    Schill Collberg, Adam
    Linköpings universitet, Matematiska institutionen. Linköpings universitet, Tekniska högskolan.
    The last two digits of mk2012Självständigt arbete på grundnivå (kandidatexamen), 10,5 poäng / 16 hpStudentuppsats (Examensarbete)
    Abstract [en]

    In this thesis the last two digits of m^k, for different cases of the positive integers m and k, in the base of 10 has been determined. Moreover, using fundamental theory from elementary number theory and abstract algebra, results most helpful in finding the last two digits in any base b has been regarded and developed, such as how to reduce large m and k to more manageable numbers.

  • 40.
    Stokes, Klara
    Universitat Rovira i Virgili, Catalonia, Spain.
    k-Anonimidad para grafos2012Konferensbidrag (Övrigt vetenskapligt)
  • 41.
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    Numerical semigroups from combinatorial configurations2012Konferensbidrag (Övrigt vetenskapligt)
  • 42. Stokes, Klara
    On computational anonymity2012Ingår i: Privacy in Statistical Databases 2012: UNESCO Chair in Data Privacy, International Conference, PSD 2012, Palermo, Italy, September 26-28, 2012. Proceedings / [ed] Josep Domingo-Ferrer and Ilenia Tinnirello, Springer, 2012, 7556, s. 336-347Kapitel i bok, del av antologi (Refereegranskat)
  • 43.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Associating a numerical semigroup to the triangle-free configurations2011Ingår i: Advances in Mathematics of Communications, ISSN 1930-5346, E-ISSN 1930-5338, Vol. 5, nr 2, s. 351-371Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    It is proved that a numerical semigroup can be associated to the triangle-free -configurations, and some results on existence are deduced. For example it is proved that for any there exists infinitely many -configurations. Most proofs are given from a graph theoretical point of view, in the sense that the configurations are represented by their incidence graphs. An application to private information retrieval is described.

  • 44.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Combinatorial structures for an anonymous database search protocol2011Konferensbidrag (Övrigt vetenskapligt)
  • 45.
    Stokes, Klara
    et al.
    Linköpings universitet, Institutionen för datavetenskap, Databas och informationsteknik. Linköpings universitet, Tekniska högskolan.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Spain.
    Linear non-homogenous patterns and prime power generators in numerical semigroups associated to combinatorial configurations2014Ingår i: Semigroup Forum, ISSN 0037-1912, E-ISSN 1432-2137, Vol. 44, nr 1, s. 11-20Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    It is proved that the numerical semigroups associated to the combinatorial configurations satisfy a family of non-linear symmetric patterns. Also, these numerical semigroups are studied for two particular classes of combinatorial configurations.

  • 46.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain.
    On query self-submission in peer-to-peer user-private information retrieval2011Ingår i: PAIS '11 Proceedings of the 4th International Workshop on Privacy and Anonymity in the Information Society, ACM Press, 2011Konferensbidrag (Refereegranskat)
    Abstract [en]

    User-private information retrieval (UPIR) is the art of retrieving information without telling the information holder who you are. UPIR is sometimes called anonymous keyword search. This article discusses a UPIR protocol in which the users form a peer-to-peer network over which they collaborate in protecting the privacy of each other. The protocol is known as P2P UPIR. It will be explained why the P2P UPIR protocol may have a flaw in the protection of the privacy of the client in front of the server. Two alternative variations of the protocols are discussed. One of these will prove to resolve the privacy flaw discovered in the original protocol. Hence the aim of this article is to propose a modification of the P2P UPIR protocol. It is justified why the projective planes are still the optimal configurations for P2P UPIR for the modified protocol.

  • 47.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Catalonia, Spain.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Catalonia, Spain.
    Optimal configurations for peer-to-peer user-private information retrieval2010Ingår i: Computers and Mathematics with Applications, ISSN 0898-1221, E-ISSN 1873-7668, Vol. 59, nr 4, s. 1568-1577Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    User-private information retrieval systems should protect the user’s anonymity when performing queries against a database, or they should limit the servers capacity of profiling users. Peer-to-peer user-private information retrieval (P2P UPIR) supplies a practical solution: the users in a group help each other in doing their queries, thereby preserving their privacy without any need of the database to cooperate. One way to implement the P2P UPIR uses combinatoric configurations to administrate the keys needed for the private communication between the peers.

    This article is devoted to the choice of the configuration in this system. First of all we characterize the optimal configurations for the P2P UPIR and see the relationship with the projective planes as described in finite geometry. Then we give a very efficient construction of such optimal configurations, i.e. finite projective planes. We finally check that the involved graphs are Ramanujan graphs, giving an additional justification of the optimality of the constructed configurations.

  • 48.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    The semigroup of combinatorial configurations2010Konferensbidrag (Övrigt vetenskapligt)
  • 49.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Spain.
    Farràs, Oriol
    Universitat Rovira i Virgili, Spain.
    Linear spaces and transversal designs:k-anonymous combinatorial configurations for anonymous database search2012Ingår i: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 71, nr 3, s. 503-524Artikel i tidskrift (Refereegranskat)
    Abstract [en]

    Anonymous database search protocols allow users to query a database anonymously. This can be achieved by letting the users form a peer-to-peer community and post queries on behalf of each other. In this article we discuss an application of combinatorial configurations (also known as regular and uniform partial linear spaces) to a protocol for anonymous database search, as defining the key-distribution within the user community that implements the protocol. The degree of anonymity that can be provided by the protocol is determined by properties of the neighborhoods and the closed neighborhoods of the points in the combinatorial configuration that is used. Combinatorial configurations with unique neighborhoods or unique closed neighborhoods are described and we show how to attack the protocol if such configurations are used. We apply k-anonymity arguments and present the combinatorial configurations with k-anonymous neighborhoods and with k-anonymous closed neighborhoods. The transversal designs and the linear spaces are presented as optimal configurations among the configurations with k-anonymous neighborhoods and k-anonymous closed neighborhoods, respectively.

  • 50.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Spain.
    Torra, Vicenç
    Universitat Aut`onoma de Barcelona, Spain.
    On some clustering approaches for graphs2011Ingår i: Fuzzy Systems (FUZZ), 2011, IEEE , 2011, s. 409-415Konferensbidrag (Refereegranskat)
    Abstract [en]

    In this paper we discuss some tools for graph perturbation with applications to data privacy. We present and analyse two different approaches. One is based on matrix decomposition and the other on graph partitioning. We discuss these methods and show that they belong to two traditions in data protection: noise addition/microaggregation and k-anonymity.

12 1 - 50 av 54
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf