liu.seSearch for publications in DiVA
Change search
Refine search result
1 - 8 of 8
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.
    Dahllöf, Vilhelm
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Counting Satisfying Assignments in 2-SAT and 3-SAT2003Conference paper (Other academic)
    Abstract [en]

    We present an O(1.3247n) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894n) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381n) and O(1.739n) time, respectively.

  • 2.
    Dahllöf, Wilhelm
    et al.
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Jonsson, Peter
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB. Linköping University, The Institute of Technology.
    Counting models for 2sat and 3sat formulae2005In: Theoretical Computer Science, ISSN 0304-3975, Vol. 332, no 1-3, p. 265-291Article in journal (Refereed)
    Abstract [en]

    We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561n) and O(1.6737n) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247n) and O(1.6894n) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.

  • 3.
    Lagerkvist, Vicktor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
    Wahlström, Magnus
    Department of Computer Science, Royal Holloway, University of London, Great Britain.
    Zanuttini, Bruno
    GREYC, Normandie Université, UNICAEN, CNRS, ENSICAEN, Franc.
    Bounded Bases of Strong Partial Clones2015In: Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on, IEEE , 2015, p. 189-194Conference paper (Refereed)
    Abstract [en]

    Partial clone theory has successfully been applied to study the complexity of the constraint satisfaction problem parameterized by a set of relations (CSP(G)). Lagerkvist & Wahlstroï¿œm (ISMVL 2014) however shows that the partial polymorphisms of G (?P?I(G)) cannot be finitely generated for finite, Boolean G if CSP(G) is NP-hard (assuming P?NP). In this paper we consider stronger closure operators than functional composition which can generate ?P?I(G) from a finite set of partial functions, a bounded base. Determining bounded bases for finite languages provides a complete characterization of their partial polymorphisms and we provide such bases for k-SAT and 1-in-k-SAT.

  • 4.
    Lagerkvist, Victor
    et al.
    Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology. Univ London, Dept Comp Sci, London WC1E 7HU, England.
    Polynomially Closed Co-clones2014In: 2014 IEEE 44TH INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC (ISMVL 2014), IEEE Computer Society, 2014, p. 85-90Conference paper (Refereed)
    Abstract [en]

    Two well-studied closure operators for relations are based on primitive positive (p.p.) definitions and quantifier free p.p. definitions. The latter do however have limited expressiveness and the corresponding lattice of strong partial clones is uncountable. We consider implementations allowing polynomially many existentially quantified variables and obtain a dichotomy for co-clones where such implementations are enough to implement any relation and prove (1) that all remaining coclones contain relations requiring a superpolynomial amount of quantified variables and (2) that the strong partial clones corresponding to two of these co-clones are of infinite order whenever the set of invariant relations can be finitely generated.

  • 5.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Algorithms, measures and upper bounds for satisfiability and related problems2007Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of attention, particularly with the focus of producing algorithms with stronger theoretical guarantees, e.g. upper bounds on the running time on the form O(c^n) for some c. Better methods of analysis may have an impact not only on these bounds, but on the nature of the algorithms as well.

    The most classic method of analysis of the running time of DPLL-style ("branching" or "backtracking") recursive algorithms consists of counting the number of variables that the algorithm removes at every step. Notable improvements include Kullmann's work on complexity measures, and Eppstein's work on solving multivariate recurrences through quasiconvex analysis. Still, one limitation that remains in Eppstein's framework is that it is difficult to introduce (non-trivial) restrictions on the applicability of a possible recursion.

    We introduce two new kinds of complexity measures, representing two ways to add such restrictions on applicability to the analysis. In the first measure, the execution of the algorithm is viewed as moving between a finite set of states (such as the presence or absence of certain structures or properties), where the current state decides which branchings are applicable, and each branch of a branching contains information about the resultant state. In the second measure, it is instead the relative sizes of the modelled attributes (such as the average degree or other concepts of density) that controls the applicability of branchings.

    We adapt both measures to Eppstein's framework, and use these tools to provide algorithms with stronger bounds for a number of problems. The problems we treat are satisfiability for sparse formulae, exact 3-satisfiability, 3-hitting set, and counting models for 2- and 3-satisfiability formulae, and in every case the bound we prove is stronger than previously known bounds.

    List of papers
    1. Counting Satisfying Assignments in 2-SAT and 3-SAT
    Open this publication in new window or tab >>Counting Satisfying Assignments in 2-SAT and 3-SAT
    2003 (English)Conference paper, Published paper (Other academic)
    Abstract [en]

    We present an O(1.3247n) algorithm for counting the number of satisfying assignments for instances of 2-SAT and an O(1.6894n) algorithm for instances of 3-SAT. This is an improvement compared to the previously best known algorithms running in O(1.381n) and O(1.739n) time, respectively.

    Series
    Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 2387
    National Category
    Computer Sciences
    Identifiers
    urn:nbn:se:liu:diva-14394 (URN)10.1007/3-540-45655-4_57 (DOI)978-3-540-43996-7 (ISBN)
    Conference
    8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002
    Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2018-01-24
    2. Exact algorithms for finding minimum transversals in rank-3 hypergraphs
    Open this publication in new window or tab >>Exact algorithms for finding minimum transversals in rank-3 hypergraphs
    2004 (English)In: Journal of Algorithms, ISSN 0196-6774, Vol. 51, no 2, p. 107-121Article in journal (Refereed) Published
    Abstract [en]

    We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time O(1.6538n) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316n).

    Keywords
    Minimum transversal, Hypergraph, 3-Hitting Set, Exact algorithm
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-14395 (URN)10.1016/j.jalgor.2004.01.001 (DOI)
    Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2009-06-08
    3. Counting models for 2sat and 3sat formulae
    Open this publication in new window or tab >>Counting models for 2sat and 3sat formulae
    2005 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 332, no 1-3, p. 265-291Article in journal (Refereed) Published
    Abstract [en]

    We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561n) and O(1.6737n) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting non-weighted models for 2SAT and 3SAT, which run in O(1.3247n) and O(1.6894n) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.

    Keywords
    Counting models; Satisfiability; Exponential-time algorithms; Exact algorithms; Upper bounds
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-14396 (URN)10.1016/j.tcs.2004.10.037 (DOI)
    Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2017-02-23
    4. Faster exact solving of SAT formulae with a low number of occurrences per variable
    Open this publication in new window or tab >>Faster exact solving of SAT formulae with a low number of occurrences per variable
    2005 (English)In: Theory and Applications of Satisfiability Testing8th International Conference, SAT 2005, St Andrews, Scotland, June 19-23, 2005, Proceedings / [ed] Bacchus, Fahiem, Walsh, Toby, 2005, p. 309-323Conference paper, Published paper (Other academic)
    Abstract [en]

    We present an algorithm that decides the satisfiability of a formula F on CNF form in time O(1.1279(d − 2)n), if F has at most d occurrences per variable or if F has an average of d occurrences per variable and no variable occurs only once. For d ≤ 4, this is better than previous results. This is the first published algorithm that is explicitly constructed to be efficient for cases with a low number of occurrences per variable. Previous algorithms that are applicable to this case exist, but as these are designed for other (more general, or simply different) cases, their performance guarantees for this case are weaker.

    Series
    Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3569
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-14397 (URN)10.1007/11499107_23 (DOI)978-3-540-26276-3 (ISBN)
    Conference
    Theory and Applications of Satisfiability Testing, 8th International Conference, SAT 2005, St Andrews, Scotland, June 19-23
    Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2018-01-31
    5. An algorithm for the sat problem for formulae of linear length
    Open this publication in new window or tab >>An algorithm for the sat problem for formulae of linear length
    2005 (English)In: Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. / [ed] Gerth S. Brodal and Stefano Leonardi, Berlin/Heidelberg: Springer , 2005, Vol. 3669, p. 107-118Conference paper, Published paper (Other academic)
    Abstract [en]

    We present an algorithm that decides the satisfiability of a CNF formula where every variable occurs at most k times in time O(2N(1&#x2212;c/(k+1)+O(1/k2)))" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">O(2N(1−c/(k+1)+O(1/k2)))O(2N(1−c/(k+1)+O(1/k2))) for some c (that is, O(α N ) with α< 2 for every fixed k). For k ≤ 4, the results coincide with an earlier paper where we achieved running times of O(20.1736 N ) for k = 3 and O(20.3472N ) for k = 4 (for k ≤ 2, the problem is solvable in polynomial time). For k>4, these results are the best yet, with running times of O(20.4629N ) for k = 5 and O(20.5408N ) for k = 6. As a consequence of this, the same algorithm is shown to run in time O(20.0926L ) for a formula of length (i.e.total number of literals) L. The previously best bound in terms of L is O(20.1030L ). Our bound is also the best upper bound for an exact algorithm for a 3satformula with up to six occurrences per variable, and a 4sat formula with up to eight occurrences per variable.

    Place, publisher, year, edition, pages
    Berlin/Heidelberg: Springer, 2005
    Series
    Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 3669
    National Category
    Engineering and Technology
    Identifiers
    urn:nbn:se:liu:diva-14398 (URN)10.1007/11561071 (DOI)978-3-540-29118-3 (ISBN)
    Conference
    13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005.
    Available from: 2007-04-16 Created: 2007-04-16 Last updated: 2018-02-02
  • 6.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    An algorithm for the sat problem for formulae of linear length2005In: Algorithms – ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. / [ed] Gerth S. Brodal and Stefano Leonardi, Berlin/Heidelberg: Springer , 2005, Vol. 3669, p. 107-118Conference paper (Other academic)
    Abstract [en]

    We present an algorithm that decides the satisfiability of a CNF formula where every variable occurs at most k times in time O(2N(1&#x2212;c/(k+1)+O(1/k2)))" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">O(2N(1−c/(k+1)+O(1/k2)))O(2N(1−c/(k+1)+O(1/k2))) for some c (that is, O(α N ) with α< 2 for every fixed k). For k ≤ 4, the results coincide with an earlier paper where we achieved running times of O(20.1736 N ) for k = 3 and O(20.3472N ) for k = 4 (for k ≤ 2, the problem is solvable in polynomial time). For k>4, these results are the best yet, with running times of O(20.4629N ) for k = 5 and O(20.5408N ) for k = 6. As a consequence of this, the same algorithm is shown to run in time O(20.0926L ) for a formula of length (i.e.total number of literals) L. The previously best bound in terms of L is O(20.1030L ). Our bound is also the best upper bound for an exact algorithm for a 3satformula with up to six occurrences per variable, and a 4sat formula with up to eight occurrences per variable.

  • 7.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Exact algorithms for finding minimum transversals in rank-3 hypergraphs2004In: Journal of Algorithms, ISSN 0196-6774, Vol. 51, no 2, p. 107-121Article in journal (Refereed)
    Abstract [en]

    We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time O(1.6538n) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316n).

  • 8.
    Wahlström, Magnus
    Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
    Faster exact solving of SAT formulae with a low number of occurrences per variable2005In: Theory and Applications of Satisfiability Testing8th International Conference, SAT 2005, St Andrews, Scotland, June 19-23, 2005, Proceedings / [ed] Bacchus, Fahiem, Walsh, Toby, 2005, p. 309-323Conference paper (Other academic)
    Abstract [en]

    We present an algorithm that decides the satisfiability of a formula F on CNF form in time O(1.1279(d − 2)n), if F has at most d occurrences per variable or if F has an average of d occurrences per variable and no variable occurs only once. For d ≤ 4, this is better than previous results. This is the first published algorithm that is explicitly constructed to be efficient for cases with a low number of occurrences per variable. Previous algorithms that are applicable to this case exist, but as these are designed for other (more general, or simply different) cases, their performance guarantees for this case are weaker.

1 - 8 of 8
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