Hasil untuk "cs.DS"

Johannes Rauch

We describe the implementation of the exact solver weberknecht and the heuristic solver weberknecht_h for the One-Sided Crossing Minimization problem.

Raed Jaberi

Let $G=(V,E)$ be a strongly biconnected directed graph. In this paper we consider the problem of computing an edge subset $H \subseteq E$ of minimum size such that the directed subgraph $(V,H)$ is strongly biconnected.

Enoch Peserico, Michele Scquizzato

We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least $\sqrt{\log_2(n\!+\!1)}/12$ for all $n=2^i\!-\!1: i\in\mathbb{N}$.

Shai Vardi

We consider query trees of graphs with degree bounded by a constant, $d$. We give simple proofs that the size of a query tree is constant in expectation and $2^{O(d)}\log{n}$ w.h.p.

Shai Vardi

We consider the problem of sampling a proper $k$-coloring of a graph of maximal degree $Δ$ uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of bounded treewidth if $k\geq(1+ε)Δ$, for any $ε>0$.

Michael W. Mahoney

These are lecture notes that are based on the lectures from a class I taught on the topic of Spectral Graph Methods at UC Berkeley during the Spring 2015 semester.

Holger Petersen

An algorithm counting the number of ones in a binary word is presented running in time $O(\log\log b)$ where $b$ is the number of ones. The operations available include bit-wise logical operations and multiplication.

Ching-Lueh Chang

We give a deterministic $O(hn^{1+1/h})$-time $(2h)$-approximation nonadaptive algorithm for $1$-median selection in $n$-point metric spaces, where $h\in\mathbb{Z}^+\setminus\{1\}$ is arbitrary. Our proof generalizes that of Chang.

Hanlin Liu

We proposed an algorithm that covers some cases of Hamilton Circuit Problem.

Christopher A. Tucker

A model of a geometric algorithm is introduced and methodology of its operation is presented for the dynamic partitioning of data spaces.

Ton Kloks

Koivisto studied the partitioning of sets of bounded cardinality. We improve his time analysis somewhat, for the special case of triangle partitions, and obtain a slight improvement.

Florian Heigl, Clemens Heuberger

Extending an idea of Suppakitpaisarn, Edahiro and Imai, a dynamic programming approach for computing digital expansions of minimal weight is transformed into an asymptotic analysis of minimal weight expansions. The minimal weight of an optimal expansion of a random input of length $\ell$ is shown to be asymptotically normally distributed under suitable conditions. After discussing the general framework, we focus on expansions to the base of $\tau$, where $\tau$ is a root of the polynomial $X^2- \mu X + 2$ for $\mu \in \{ \pm 1\}$. As the Frobenius endomorphism on a binary Koblitz curve fulfils the same equation, digit expansions to the base of this $\tau$ can be used for scalar multiplication and linear combination in elliptic curve cryptosystems over these curves.

Guy Fayolle, Kilian Raschel

Enumeration of planar lattice walks is a classical topic in combinatorics, at the cross-roads of several domains (e.g., probability, statistical physics, computer science). The aim of this paper is to propose a new approach to obtain some exact asymptotics for walks confined to the quarter plane.

Sarah Miracle, Dana Randall, Amanda Pascoe Streib et al.

Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a $\textit{Schnyder wood}$ that has proven useful for various computing and combinatorics applications. We consider natural Markov chains for sampling uniformly from the set of 3-orientations. First, we study a "triangle-reversing'' chain on the space of 3-orientations of a fixed triangulation that reverses the orientation of the edges around a triangle in each move. We show that (i) when restricted to planar triangulations of maximum degree six, the Markov chain is rapidly mixing, and (ii) there exists a triangulation with high degree on which this Markov chain mixes slowly. Next, we consider an "edge-flipping'' chain on the larger state space consisting of 3-orientations of all planar triangulations on a fixed number of vertices. It was also shown previously that this chain connects the state space and we prove that the chain is always rapidly mixing.

Bernhard Gittenberger, Veronika Kraus

We study transversals in random trees with n vertices asymptotically as n tends to infinity. Our investigation treats the average number of transversals of fixed size, the size of a random transversal as well as the probability that a random subset of the vertex set of a tree is a transversal for the class of simply generated trees and for Pólya trees. The last parameter was already studied by Devroye for simply generated trees. We offer an alternative proof based on generating functions and singularity analysis and extend the result to Pólya trees.

Gleb Novichkov

A linear time algorithm to find a set of nearest elements in a mesh.

Ton Kloks, Yue-Li Wang

We show that there exists a linear-time algorithm that computes the strong chromatic index of Halin graphs.

Leo Lahti

A brief informal overview on the BioPAX and SBML standards for formal presentation of complex biological knowledge.

Hyung-Chan An, David B. Shmoys

This paper has been merged into 1110.4604.

Golnaz Ghasemiesfeh, Hanieh Mirzaei, Yahya Tabesh

This article has been withdrawn.