Results 11 to 20 of about 985 (69)
A robust p-Center problem under pressure to locate shelters in wildfire context
EURO Journal on Computational Optimization, 2020 The location of shelters in different areas threatened by wildfires is one of the possible ways to reduce fatalities in a context of an increasing number of catastrophic and severe wildfires.
Marc Demange +3 more
doaj +1 more source
The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polynomial time algorithms for special cases.
Michael H. Albert +3 more
doaj +1 more source
Packing a bin online to maximize the total number of items [PDF]
, 1996 A bin of capacity 1 and a nite sequence of items of\ud sizes a1; a2; : : : are considered, where the items are given one by one\ud without information about the future.
Faigle, Ulrich, Kern, Walter
core +3 more sources
Bipartite graphs with close domination and k-domination numbers
Open Mathematics, 2020 Let kk be a positive integer and let GG be a graph with vertex set V(G)V(G). A subset D⊆V(G)D\subseteq V(G) is a kk-dominating set if every vertex outside DD is adjacent to at least kk vertices in DD. The kk-domination number γk(G){\gamma }_{k}(G) is the
Ekinci Gülnaz Boruzanlı +1 more
doaj +1 more source
The Subpower Membership Problem for Finite Algebras with Cube Terms [PDF]
Logical Methods in Computer Science, 2019 The subalgebra membership problem is the problem of deciding if a given element belongs to an algebra given by a set of generators. This is one of the best established computational problems in algebra.
Andrei Bulatov +2 more
doaj +1 more source
Two Compact Incremental Prime Sieves [PDF]
, 2015 A prime sieve is an algorithm that finds the primes up to a bound $n$. We say that a prime sieve is incremental, if it can quickly determine if $n+1$ is prime after having found all primes up to $n$. We say a sieve is compact if it uses roughly $\sqrt{n}$
Sorenson, Jonathan P.
core +3 more sources
A variant of the large sieve inequality with explicit constants
Journal of Mathematical Cryptology, 2020 We give an effective version with explicit constants of the large sieve inequality for imaginary quadratic fields. Explicit results of this kind are useful for estimating the computational complexity of algorithms which generate elements, whose norm is a
Grześkowiak Maciej
doaj +1 more source
Pushing for weighted tree automata [PDF]
Logical Methods in Computer Science, 2018 A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful ...
Thomas Hanneforth +2 more
doaj +1 more source
On the Complexity of Finding a Sun in a Graph [PDF]
, 2010 The sun is the graph obtained from a cycle of length even and at least six by adding edges to make the even-indexed vertices pairwise adjacent. Suns play an important role in the study of strongly chordal graphs. A graph is chordal if it does not contain
Hoàng, Chính T.
core +2 more sources
A Decomposition Theorem for Maximum Weight Bipartite Matchings [PDF]
, 1999 Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of G. Let k(x,y) be log(x)/log(x^2/y). We present a new decomposition theorem
Kao, Ming-Yang +3 more
core +3 more sources