liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 48 of 48
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 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 transversals2014In: Computational Geometry, ISSN 0925-7721, Vol. 47, no 2, p. 224-239Article in journal (Refereed)
    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öping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Casselgren, Carl Johan
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering. University of Southern Denmark, Denmark.
    Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results2016In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 82, no 4, p. 350-373Article in journal (Refereed)
    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öping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Casselgren, Carl Johan
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Petrosyan, Petros A.
    Yerevan State University, Armenia; National Academic Science, Armenia.
    Some results on cyclic interval edge colorings of graphs2018In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 87, no 2, p. 239-252Article in journal (Refereed)
    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 pentagon2013In: Journal of combinatorial designs (Print), ISSN 1063-8539, E-ISSN 1520-6610, Vol. 21, no 4, p. 163-179Article in journal (Refereed)
    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.
    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 pares2009Conference paper (Other academic)
  • 6.
    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 configurations2010In: 3rd International Workshop on Optimal Networks Topologies, 2010, 2010, p. 145-167Conference paper (Other academic)
  • 7.
    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 configurations2012In: Semigroup Forum, ISSN 0037-1912, E-ISSN 1432-2137, Vol. 84, no 1, p. 91-96Article in journal (Refereed)
    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.

  • 8.
    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 retrieval2010Conference paper (Other academic)
  • 9.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014Report (Other academic)
    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.

  • 10.
    Burdakov, Oleg
    et al.
    Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
    Doherty, Patrick
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Kvarnström, Jonas
    Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, The Institute of Technology.
    Local Search for Hop-constrained Directed Steiner Tree Problem with Application to UAV-based Multi-target Surveillance2014In: Examining Robustness and Vulnerability of Networked Systems / [ed] Butenko, S., Pasiliao, E.L., Shylo, V., IOS Press, 2014, p. 26-50Conference paper (Refereed)
    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.

  • 11.
    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öping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering. 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 Games2016In: DISCRETE AND COMPUTATIONAL GEOMETRY AND GRAPHS, JCDCGG 2015 / [ed] Akiyama, J., Ito, H., Sakai, T., Uno, Y., SPRINGER INT PUBLISHING AG , 2016, Vol. 9943, p. 60-72Conference paper (Refereed)
    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.

  • 12.
    Bäckström, Christer
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Time and Space Bounds for Planning2017In: The journal of artificial intelligence research, ISSN 1076-9757, E-ISSN 1943-5037, Vol. 60, p. 595-638Article in journal (Refereed)
    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.

  • 13.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Haggkvist, Roland
    Umeå University, Sweden.
    Coloring Complete and Complete Bipartite Graphs from Random Lists2016In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, p. 533-542Article in journal (Refereed)
    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.

  • 14.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    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 graphs2018In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 341, no 3, p. 627-637Article in journal (Refereed)
    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.

    The full text will be freely available from 2019-11-27 16:26
  • 15.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    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 graphs2017In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 340, no 11, p. 2678-2687Article in journal (Refereed)
    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.

    The full text will be freely available from 2018-09-15 14:12
  • 16.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Sune Pedersen, Anders
    University of Southern Denmark, Denmark; Aarhus University Hospital, Denmark.
    Hadwigers Conjecture for inflations of 3-chromatic graphs2016In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 51, p. 99-108Article in journal (Refereed)
    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.

  • 17.
    Casselgren, Carl Johan
    et al.
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering. University of Southern Denmark, Denmark.
    Toft, Bjarne
    University of Southern Denmark, Denmark.
    One-sided interval edge-colorings of bipartite graphs2016In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 339, no 11, p. 2628-2639Article in journal (Refereed)
    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.

  • 18.
    Eriksson, T.
    et al.
    Linköping University, Department of Electrical Engineering. Linköping University, The Institute of Technology.
    Körner, J.
    Bell Laboratories, Murray Hill, USA / Mathematical Institute of the Hungari an Academy of Sciences, Budapest, Hungary.
    Successive Encoding of Correlated Sources1982Report (Other academic)
    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.

  • 19.
    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öping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
    Troegel, Julian
    TU Braunschweig, Germany.
    Computing Nonsimple Polygons of Minimum Perimeter2016In: EXPERIMENTAL ALGORITHMS, SEA 2016, SPRINGER INT PUBLISHING AG , 2016, Vol. 9685, p. 134-149Conference paper (Refereed)
    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.

  • 20.
    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 Navigation2014In: Proceedings from the 2013 International Symposium on Vehicle, Mechanical, and Electrical Engineering, ISVMEE 2013, Taiwan, China, 21-22 December, 2014, Vol. 494-495, p. 1080-1083Conference paper (Refereed)
    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.

  • 21.
    Glasser, Christian
    et al.
    Julius Maximilian University, Germany.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Martin, Barnaby
    University of Durham, England.
    Circuit satisfiability and constraint satisfaction around Skolem Arithmetic2017In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 703, p. 18-36Article in journal (Refereed)
    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.

  • 22.
    Granholm, Jonas
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Some cyclic properties of graphs with local Ore-type conditions2016Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    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.

  • 23.
    Hansson, Mikael
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Generalised Ramsey numbers for two sets of cycles2018In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 238, p. 86-94Article in journal (Refereed)
    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.

    The full text will be freely available from 2020-01-06 13:08
  • 24.
    Hultman, Axel
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Supersolvability and the Koszul property of root ideal arrangements2016In: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 144, p. 1401-1413Article in journal (Refereed)
    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.

  • 25.
    Izquierdo, Milagros
    et al.
    Linköping University, Department of Mathematics. Linköping University, Faculty of Science & Engineering.
    Stokes, Klara
    Högskolan i Skövde.
    Isometric Point-Circle Configurations on Surfaces from Uniform Maps2016In: Springer Proceedings in Mathematics and Statistics, ISSN 2194-1009, Vol. 159, p. 201-212Article in journal (Refereed)
    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.

  • 26.
    Jonsson, Peter
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Thapper, Johan
    Univ Paris Est Marne la Vallee, France.
    Tractability conditions for numeric CSPs2018In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 715, p. 21-34Article in journal (Refereed)
    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.

  • 27.
    Kamalian, Rafayel
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    On a number of colors in cyclically interval edgecolorings of trees2010Report (Other academic)
    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.

  • 28.
    Karlsson, Patrik
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    Diskret krökning, en jämförelse2012Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
    Abstract [en]

    In this thesis we analyze and compare two different methods for approximating the Gauss and mean curvature on a surface, which is given as a set of points. It is important to find a method that agrees well with the analytic Gauss and mean curvatures and guarantees robust estimations. There is a great interest in Gauss and mean curvature since these two curvatures give information about the local geometry of the surface around the point at which these curvatures are calculated.

    The thesis begins with a short overview of differential theory and then the methods are explained and described. The reason for this is to give the reader an understanding of the theory before explaining the methods.

    The first method is called Bézier surfaces, which interpolates the given points. These surfaces are differentiable which makes it possible to approximate the Gauss and mean curvature, and are therefore very well suited for our problem.

    The second method comes from the research article ``Discrete Differential-Geometry Operators for Triangulated 2-Manifolds'' by Mark Meyer, Mathieu Desbrun, Peter Schröder and Alan H. Barr. Their algorithm requires a triangulated surface, which itself is a hard problem to solve (at least if one has requirements on the triangulation). Their approximations of the Gauss and mean curvatures use a well chosen area around the point, and the Gauss curvature also makes use of the Gauss-Bonnet theorem.

    My simulations show that Bézier surfaces approximate both Gauss and mean curvature well, and the approximations seem to converge to the analytic value when the information gets better. The articles algorithm also works well for approximating both curvatures, though this method seems to depend somewhat on the triangulation. This gives some requirements on the triangulation and will therefore be a harder problem to solve. The approximations do not converge when given a triangulation with obtuse triangles, though it shows signs to do so.

  • 29.
    Kurujyibwami, Celestin
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
    Admissible transformations and the group classification of Schrödinger equations2017Doctoral thesis, comprehensive summary (Other academic)
    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.

    List of papers
    1. Equivalence groupoid for (1+2)-dimensional linear Schrodinger equations with complex potentials
    Open this publication in new window or tab >>Equivalence groupoid for (1+2)-dimensional linear Schrodinger equations with complex potentials
    2015 (English)In: SEVENTH INTERNATIONAL WORKSHOP: GROUP ANALYSIS OF DIFFERENTIAL EQUATIONS AND INTEGRABLE SYSTEMS (GADEISVII), IOP Publishing: Conference Series / Institute of Physics (IoP) , 2015, Vol. 621, no UNSP 012008, p. UNSP 012008-Conference paper, Published paper (Refereed)
    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.

    Place, publisher, year, edition, pages
    IOP Publishing: Conference Series / Institute of Physics (IoP), 2015
    Series
    Journal of Physics Conference Series, ISSN 1742-6588 ; 621
    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-120668 (URN)10.1088/1742-6596/621/1/012008 (DOI)000357939100008 ()
    Conference
    7th International Workshop on Group Analysis of Differential Equations and Integrable Systems (GADEIS)
    Available from: 2015-08-20 Created: 2015-08-20 Last updated: 2017-05-15
  • 30.
    Lundqvist, Anders
    Linköping University, Department of Electrical Engineering, Data Transmission. Linköping University, The Institute of Technology.
    Cyclically permutable codes1997Doctoral thesis, monograph (Other academic)
    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.

  • 31.
    Ogniewski, Jens
    Linköping University, Department of Electrical Engineering, Information Coding. Linköping University, Faculty of Science & Engineering.
    Artifact-Free Color Interpolation2015In: Proceedings SCCG: 2015 31st Spring Conference on Computer Graphics, ASSOC COMPUTING MACHINERY , 2015, p. 116-119Conference paper (Refereed)
    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.

  • 32.
    Rahm, Ludwig
    Linköping University, Department of Mathematics, Mathematics and Applied Mathematics.
    Generating functions and regular languages of walks with modular restrictions in graphs2017Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
    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.

  • 33.
    Schill Collberg, Adam
    Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
    The last two digits of mk2012Independent thesis Basic level (degree of Bachelor), 10,5 credits / 16 HE creditsStudent thesis
    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.

  • 34.
    Stokes, Klara
    Universitat Rovira i Virgili, Catalonia, Spain.
    k-Anonimidad para grafos2012Conference paper (Other academic)
  • 35.
    Stokes, Klara
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    Numerical semigroups from combinatorial configurations2012Conference paper (Other academic)
  • 36. Stokes, Klara
    On computational anonymity2012In: 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, p. 336-347Chapter in book (Refereed)
  • 37.
    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 configurations2011In: Advances in Mathematics of Communications, ISSN 1930-5346, E-ISSN 1930-5338, Vol. 5, no 2, p. 351-371Article in journal (Refereed)
    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.

  • 38.
    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 protocol2011Conference paper (Other academic)
  • 39.
    Stokes, Klara
    et al.
    Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
    Bras-Amorós, Maria
    Universitat Rovira i Virgili, Spain.
    Linear non-homogenous patterns and prime power generators in numerical semigroups associated to combinatorial configurations2014In: Semigroup Forum, ISSN 0037-1912, E-ISSN 1432-2137, Vol. 44, no 1, p. 11-20Article in journal (Refereed)
    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.

  • 40.
    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 retrieval2011In: PAIS '11 Proceedings of the 4th International Workshop on Privacy and Anonymity in the Information Society, ACM Press, 2011Conference paper (Refereed)
    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.

  • 41.
    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 retrieval2010In: Computers and Mathematics with Applications, ISSN 0898-1221, E-ISSN 1873-7668, Vol. 59, no 4, p. 1568-1577Article in journal (Refereed)
    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.

  • 42.
    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 configurations2010Conference paper (Other academic)
  • 43.
    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 search2012In: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 71, no 3, p. 503-524Article in journal (Refereed)
    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.

  • 44.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Spain.
    Torra, Vicenç
    Universitat Aut`onoma de Barcelona, Spain.
    On some clustering approaches for graphs2011In: Fuzzy Systems (FUZZ), 2011, IEEE , 2011, p. 409-415Conference paper (Refereed)
    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.

  • 45.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Spain.
    Torra, Vicenç
    Universitat Aut`onoma de Barcelona, Spain.
    On the Relationship Between Clustering and Coding Theory2012Conference paper (Refereed)
    Abstract [en]

    In this paper we discuss the relations between clustering and error correcting codes. We show that clustering can be used for constructing error correcting codes. We review the previous works found in the literature about this issue, and propose a modification of a previous work that can be used for code construction from a set of proposed codewords.

  • 46.
    Stokes, Klara
    et al.
    Universitat Rovira i Virgili, Tarragona, Catalonia, Spain .
    Torra, Vicenç
    IIIA, Institut d’Investigació en Intel ligència Artificial CSIC, Bellaterra, Catalonia, Spain .
    Reidentification and k-anonymity: a model for disclosure risk in graphs2012In: Soft Computing - A Fusion of Foundations, Methodologies and Applications, ISSN 1432-7643, E-ISSN 1433-7479, Vol. 16, no 10, p. 1657-1670Article in journal (Refereed)
    Abstract [en]

    In this article we provide a formal framework for reidentification in general. We define n-confusion as a concept for modeling the anonymity of a database table and we prove that n-confusion is a generalization of k-anonymity. After a short survey on the different available definitions of k-anonymity for graphs we provide a new definition for k-anonymous graph, which we consider to be the correct definition. We provide a description of the k-anonymous graphs, both for the regular and the non-regular case. We also introduce the more flexible concept of (k, l)-anonymous graph. Our definition of (k, l)-anonymous graph is meant to replace a previous definition of (k, l)-anonymous graph, which we here prove to have severe weaknesses. Finally, we provide a set of algorithms for k-anonymization of graphs.

  • 47.
    Thapper, Johan
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Combinatorial Considerations on Two Models from Statistical Mechanics2007Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years.

    The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp.

    The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.

    List of papers
    1. Refined Counting of Fully Packed Loop Configurations
    Open this publication in new window or tab >>Refined Counting of Fully Packed Loop Configurations
    2007 (English)In: Séminaire Lotharingien de Combinatoire, ISSN 1286-4889, Vol. 56, p. 1-27Article in journal (Refereed) Published
    Abstract [en]

    We give a generalisation of a conjecture by Propp on a summation formula for fully packed loop configurations. The original conjecture states that the number of configurations in which each external edge is connected to its neighbour is equal to the total number of configurations of size one less. This conjecture was later generalised by Zuber to include more types of configurations. Our conjecture further refines the counting and provides a general framework for some other summation formulas observed by Zuber. It also implies similar summation formulas for half-turn symmetric configurations.

    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-12703 (URN)
    Available from: 2007-10-29 Created: 2007-10-29
    2. Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs
    Open this publication in new window or tab >>Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs
    (English)Manuscript (Other academic)
    Abstract [en]

    In the paper [Fendley et al., J. Phys. A: Math. Gen., 38 (2005), pp. 315-322], Fendley, Schoutens and van Eerten studied the hard square model at negative activity. They found analytical and numerical evidence that the eigenvalues of the transfer matrix with periodic boundary were all roots of unity. They also conjectured that for an m × n square grid, with doubly periodic boundary, the partition function is equal to 1 when m and n are relatively prime. These conjectures were proven in [Jonsson, Electronic J. Combin., 13(1) (2006), R67]. There, it was also noted that the cylindrical case seemed to have interesting properties when the circumference of the cylinder is odd. In particular, when 3 is a divisor of both the circumference and the width of the cylinder minus 1, the partition function is -2. Otherwise, it is equal to 1. In this paper, we investigate the hard square and hard hexagon models at activity -1, with single periodic boundary, i.e, cylindrical identifications, using both topological and combinatorial techniques. We compute the homology groups of the associated independence complex for small sizes and suggest a matching which, we believe, with further analysis could help solve the conjecture. We also briefly review a technique recently described by Bousquet-M´elou, Linusson and Nevo, for determining some of the eigenvalues of the transfer matrix of the hard square model with cylindrical identification using a related, but more easily analysed model.

    National Category
    Mathematics
    Identifiers
    urn:nbn:se:liu:diva-12704 (URN)
    Available from: 2007-10-29 Created: 2007-10-29Bibliographically approved
  • 48.
    Won Bae, Sang
    et al.
    Kyonggi University, South Korea.
    Korman, Matias
    Tohoku University, Japan.
    Mitchell, Joseph S. B.
    SUNY Stony Brook, NY USA.
    Okamoto, Yoshio
    University of Electrocommun, Japan.
    Polishchuk, Valentin
    Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
    Wang, Haitao
    Utah State University, UT 84322 USA.
    Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain2017In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 57, no 3, p. 674-701Article in journal (Refereed)
    Abstract [en]

    For a polygonal domain with h holes and a total of n vertices, we present algorithms that compute the geodesic diameter in time and the geodesic center in time, respectively, where denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in or time, and compute the geodesic center in time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on shortest paths in polygonal domains.

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