SwePub
Sök i SwePub databas

  Extended search

Träfflista för sökning "hsv:(NATURVETENSKAP) hsv:(Matematik) hsv:(Diskret matematik) ;lar1:(lu)"

Search: hsv:(NATURVETENSKAP) hsv:(Matematik) hsv:(Diskret matematik) > Lund University

  • Result 1-10 of 29
Sort/group result
   
EnumerationReferenceCoverFind
1.
  • Kurasov, Pavel (author)
  • Can One Distinguish Quantum Trees From The Boundary?
  • 2012
  • In: Proceedings of the American Mathematical Society. - 1088-6826 .- 0002-9939. ; 140:7, s. 2347-2356
  • Journal article (peer-reviewed)abstract
    • Schrodinger operators on metric trees are considered. It is proven that for certain matching conditions the Titchmarsh-Weyl matrix function does not determine the underlying metric tree; i.e. there exist quantum trees with equal Titchmarsh-Weyl functions. The constructed trees form one-parameter families of isospectral and isoscattering graphs.
  •  
2.
  • Danielsson, Joel Larsson, et al. (author)
  • Polarised random κ-SAT
  • 2023
  • In: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 32:6, s. 885-899
  • Journal article (peer-reviewed)abstract
    • In this paper we study a variation of the random κ-SAT problem, called polarised random κ-SAT, which contains both the classical random κ-SAT model and the random version of monotone κ-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random κ-SAT model, and at the other extreme we have the fully polarised model where p = 0, or 1. Here there are only two types of clauses: clauses where all κ variables occur pure, and clauses where all κ variables occur negated. That is, for p = 0, and p=1, we get an instance of random monotone κ-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarised random κ-SAT with p ≠ 1/2 is an upper bound on the threshold for random κ-SAT. Hence the satisfiability threshold for random monotone κ-SAT is at least as large as for random κ-SAT, and we conjecture that asymptotically, for a fixed κ, the two thresholds coincide.
  •  
3.
  • Danielsson, Joel, et al. (author)
  • Polarised random k-SAT
  • 2022
  • Other publication (other academic/artistic)abstract
    • In this paper we study a variation of the random k-SAT problem, called polarized random k-SAT. In this model there is a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p=1/2 we get the classical random k-SAT model, and at the other extreme we have the fully polarized model where p=0, or 1. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated. That is, for p=0 we get an instance of random monotone k-SAT. We show that the threshold of satisfiability does not decrease as p moves away from 1/2 and thus that the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for random k-SAT. In fact, we conjecture that asymptotically the two thresholds coincide.
  •  
4.
  • Federico, Lorenzo, et al. (author)
  • Minimal H-factors and covers
  • 2023
  • Other publication (other academic/artistic)abstract
    • Given a fixed small graph H and a larger graph G, an H-factor is a collection of vertex-disjoint subgraphs H′⊂G, each isomorphic to H, that cover the vertices of G. If G is the complete graph Kn equipped with independent U(0,1) edge weights, what is the lowest total weight of an H-factor? This problem has previously been considered for e.g. H=K2. We show that if H contains a cycle, then the minimum weight is sharply concentrated around some Ln=Θ(n^(1−1/d∗)) (where d∗ is the maximum 1-density of any subgraph of H). Some of our results also hold for H-covers, where the copies of H are not required to be vertex-disjoint.
  •  
5.
  •  
6.
  • Atserias, Albert, et al. (author)
  • Clique Is Hard on Average for Regular Resolution
  • 2021
  • In: Journal of the ACM. - : Association for Computing Machinery (ACM). - 0004-5411 .- 1557-735X. ; 68:4, s. 1-26
  • Journal article (peer-reviewed)abstract
    • We prove that for k ≫; 4√n regular resolution requires length nω(k) to establish that an ErdÅ's-Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional nω(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.
  •  
7.
  •  
8.
  • Björklund, Andreas, et al. (author)
  • A faster hafnian formula for complex matrices and its benchmarking on a supercomputer
  • 2019
  • In: ACM Journal of Experimental Algorithmics. - : Association for Computing Machinery (ACM). - 1084-6654. ; 24:1
  • Journal article (peer-reviewed)abstract
    • We introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of n × n complex matrices run in O(n32n/2) time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size 56 × 56 indicate that one would require the 288,000 CPUs of this machine for about 6 weeks to compute the hafnian of a 100 × 100 matrix.
  •  
9.
  • Björklund, Andreas, et al. (author)
  • Approximate counting of K-paths : Deterministic and in polynomial space
  • 2019
  • In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. - 9783959771092 ; 132
  • Conference paper (peer-reviewed)abstract
    • A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊−2)-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊−1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊−2)-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4k+O(√k(log2 k+log2 ∊−1))m log n-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. Additionally, we present a randomized 4k+O(log k(log k+log ∊−1))m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4k+o(k)m whenever ∊−1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊−1 = 2o(k 4 ) and 1 ∊−1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(1)-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.
  •  
10.
  • Björklund, Andreas, et al. (author)
  • Shortest two disjoint paths in polynomial time
  • 2019
  • In: SIAM Journal on Computing. - 0097-5397. ; 48:6, s. 1698-1710
  • Journal article (peer-reviewed)abstract
    • Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{1, 2}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt
  •  
Skapa referenser, mejla, bekava och länka
  • Result 1-10 of 29
Type of publication
journal article (14)
conference paper (11)
other publication (3)
doctoral thesis (1)
Type of content
peer-reviewed (25)
other academic/artistic (4)
Author/Editor
Lingas, Andrzej (5)
Björklund, Andreas (5)
Husfeldt, Thore (4)
de Rezende, Susanna ... (3)
Nordström, Jakob (3)
Lundell, Eva-Marta (3)
show more...
Markström, Klas (2)
Risse, Kilian (2)
Floderus, Peter (2)
Zehavi, Meirav (2)
Leonardi, Stefano (2)
Leander, Gregor (1)
Baier, Christel (1)
Shtarkov, Yu M. (1)
Smeets, B. J.M. (1)
Myreen, Magnus, 1983 (1)
Tan, Yong Kiam (1)
Aziz, Imran (1)
Magnusson, Måns (1)
Åberg, Jan (1)
Kurasov, Pavel (1)
Aliakbari Abar, Hani ... (1)
Gudmundsson, Sigmund ... (1)
Andersson, Karl Gust ... (1)
Levcopoulos, Christo ... (1)
Ekström, Henrik (1)
Oskarsson, Magnus (1)
Cui, Weiwei (1)
Atserias, Albert (1)
Bonacina, Ilario (1)
Lauria, Massimo (1)
Razborov, Alexander (1)
Kaski, Petteri (1)
Liao, Wan-Chun, 1985 (1)
Simon, Winfried (1)
Gocht, Stephan (1)
Oertel, Andy (1)
Gupta, Anupam (1)
Gupt, Brajesh (1)
Quesada, Nicolás (1)
Lokshtanov, Daniel (1)
Saurabh, Saket (1)
Chatzigiannakis, Ioa ... (1)
Flocchini, Paola (1)
Kowalik, Lukasz (1)
Kamat, Vikram (1)
McCreesh, Ciaran (1)
Brand, Cornelius (1)
Dell, Holger (1)
Sledneu, Dzmitry (1)
show less...
University
Chalmers University of Technology (2)
Umeå University (1)
Royal Institute of Technology (1)
Uppsala University (1)
Stockholm University (1)
Language
English (29)
Research subject (UKÄ/SCB)
Natural sciences (29)
Engineering and Technology (4)

Year

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view