Hasil untuk "cs.DS"

Yota Otachi

We show that the spanning tree congestion problem is NP-complete even for proper interval graphs of linear clique-width at most 4.

Frederic Gillet

Interpretation of 3-SAT as a volume filling problem, and its use to explore the SAT/UNSAT phase transition.

Daniel W. Cranston

Let $G$ be a planar graph and $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a "token" on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ to $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono to be fixed-parameter tractable. That is, when $k$ is fixed, the problem can be solved in time polynomial in the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a planar graph into an equivalent problem on a (planar) graph with order $O(k)$.

David Walker

This paper presents algorithms and pseudocode for encoding and decoding 3D Hilbert orderings.

Laurent Théry

This notes explains how standard algorithms that construct sorting networks have been formalised and proved correct in the Coq proof assistant using the SSReflect extension.

Andrew Frohmader

This brief note presents two adaptive heap data structures and conjectures on running times.

I. A. Junussov

Hashing algorithm of dynamical set of distances is described. Proposed hashing function is residual. Data structure which implementation accelerates computations is presented

Ching-Lueh Chang

Consider the problem of finding a point in an ultrametric space with the minimum average distance to all points. We give this problem a Monte Carlo $O((\log^2(1/ε))/ε^3)$-time $(1+ε)$-approximation algorithm for all $ε>0$.

Torben Hagerup

It is shown that a breadth-first search in a directed or undirected graph with $n$ vertices and $m$ edges can be carried out in $O(n+m)$ time with $n\log_2 3+O((\log n)^2)$ bits of working memory.

Cristian Dumitrescu

In this paper, we study an extension of Schoning's algorithm [Schoning, 1991] for 3SAT, the clustered Sparrow algorithm We also present strong arguments that this algorithm is polynomial.

Pedro Recuero

We present an algorithm that, on input $n$, lists every unlabeled tree of order $n$.

Kunihiro Wasa

In this paper, we enumerate enumeration problems and algorithms. This survey is under construction. If you know some results not in this survey or there is anything wrong, please let me know.

Justin Thaler

We survey models and algorithms for stream verification.

Dmitry Kosolobov

We present a linear time and space algorithm computing the leftmost critical factorization of a given string on an unordered alphabet.

Ching-Lueh Chang

Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic $o(n^2)$-query $(4-Ω(1))$-approximation algorithms.

Julius D'souza

A string-like compact data structure for unlabelled rooted trees is given using 2n bits.

Ton Kloks

We show that there exists a polynomial algorithm to pack interval graphs with vertex-disjoint triangles.

Olivier Bodini, Antoine Genitrini, Frédéric Peschanski

In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number of nodes) of shuffle trees. We notice, rather unexpectedly, that only a small ratio of all nodes do not belong to the last two levels. We also provide a precise characterization of what ``exponential growth'' means in the case of the shuffle on trees. Two practical outcomes of our quantitative study are presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random generation of concurrent runs.

Markus Kuba, Alois Panholzer

We use death processes and embeddings into continuous time in order to analyze several urn models with a diminishing content. In particular we discuss generalizations of the pill's problem, originally introduced by Knuth and McCarthy, and generalizations of the well known sampling without replacement urn models, and OK Corral urn models.

John Kieffer

Let $k≥2$ be a fixed integer. Given a bounded sequence of real numbers $(a_n:n≥k)$, then for any sequence $(f_n:n≥1)$ of real numbers satisfying the divide-and-conquer recurrence $f_n = (k-mod(n,k))f_⌊n/k⌋+mod(n,k)f_⌈n/k⌉ + a_n, n ≥k$, there is a unique continuous periodic function $f^*:\mathbb{R}→\mathbb{R}$ with period 1 such that $f_n = nf^*(\log _kn)+o(n)$. If $(a_n)$ is periodic with period $k, a_k=0$, and the initial conditions $(f_i:1 ≤i ≤k-1)$ are all zero, we obtain a specific iterated function system $S$, consisting of $k$ continuous functions from $[0,1]×\mathbb{R}$ into itself, such that the attractor of $S$ is $\{(x,f^*(x)): 0 ≤x ≤1\}$. Using the system $S$, an accurate plot of $f^*$ can be rapidly obtained.