Journal: Algorithmica

Found 758 papers in total
Program Size and Temperature in Self-Assembly
Program Size and Temperature in Self-Assembly
2015,
Winfree’s abstract Tile Assembly Model is a model of molecular...
Local Embeddings of Metric Spaces
Local Embeddings of Metric Spaces
2015,
In many application areas, complex data sets are often represented by some metric...
A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows
A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows
2015,
We present a new approach to the minimum‐cost integral flow problem for small...
The Approximate Rectangle of Influence Drawability Problem
The Approximate Rectangle of Influence Drawability Problem
2015,
Let ϵ 1 , ϵ 2 be two non negative numbers. An approximate rectangle of...
Angle-Restricted Steiner Arborescences for Flow Map Layout
Angle-Restricted Steiner Arborescences for Flow Map Layout
2015,
We introduce a new variant of the geometric Steiner arborescence problem, motivated by...
Hitting All Maximal Independent Sets of a Bipartite Graph
Hitting All Maximal Independent Sets of a Bipartite Graph
2015,
We prove that given a bipartite graph G with vertex set V and an integer k , deciding...
Worst-Case Optimal Tree Layout in External Memory
Worst-Case Optimal Tree Layout in External Memory
2015,
Consider laying out a fixed‐topology binary tree of N nodes into external...
Optimal Point Movement for Covering Circular Regions
Optimal Point Movement for Covering Circular Regions
2015,
Given n points in a circular region C in the plane, we study the problems of moving...
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities
2015,
A signed majority function is a linear threshold function f :{+1,−1} n...
Resequencing a Set of Strings Based on a Target String
Resequencing a Set of Strings Based on a Target String
2015,
Given a set S ={ S 1 , S 2 ,…, S l } of l strings, a text T , and a natural...
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
2015,
Suffix trees and suffix arrays are two of the most widely used data structures for...
Communication Complexity of Quasirandom Rumor Spreading
Communication Complexity of Quasirandom Rumor Spreading
2015,
We consider rumor spreading on random graphs and hypercubes in the quasirandom phone...
Approximability of Capacitated Network Design
Approximability of Capacitated Network Design
2015,
In the capacitated survivable network design problem (Cap‐SNDP), we are given...
Compressing Dictionary Matching Index via Sparsification Technique
Compressing Dictionary Matching Index via Sparsification Technique
2015,
Given a set 𝒟 of patterns of total length n , the dictionary matching problem is...
Finding and Counting Vertex-Colored Subtrees
Finding and Counting Vertex-Colored Subtrees
2013,
The problems studied in this article originate from the Graph Motif problem introduced...
Computing a Hamiltonian Path of Minimum Euclidean Length Inside a Simple Polygon
Computing a Hamiltonian Path of Minimum Euclidean Length Inside a Simple Polygon
2013,
Given an n ‐vertex convex polygon, we show that a shortest Hamiltonian path...
On the Grundy and b-Chromatic Numbers of a Graph
On the Grundy and b-Chromatic Numbers of a Graph
2013,
The Grundy number of a graph G , denoted by Γ ( G ), is the largest k such that...
Improved Approximation Algorithms for the Spanning Star Forest Problem
Improved Approximation Algorithms for the Spanning Star Forest Problem
2013,
A star graph is a tree of diameter at most two. A star forest is a graph that consists...
The Parameterized Complexity of Unique Coverage and Its Variants
The Parameterized Complexity of Unique Coverage and Its Variants
2013,
In this paper we study the parameterized complexity of the Unique Coverage problem, a...
Parameterized Two-Player Nash Equilibrium
Parameterized Two-Player Nash Equilibrium
2013,
We study the problem of computing Nash equilibria in a two‐player normal form...
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
Approximation Algorithms for the Directed k-Tour and k-Stroll Problems
2013,
We consider two natural generalizations of the Asymmetric Traveling Salesman problem:...
Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots
Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots
2013,
We consider the problem of exploring an anonymous unoriented ring by a team of k...
Computing Optimal Steiner Trees in Polynomial Space
Computing Optimal Steiner Trees in Polynomial Space
2013,
Given an n ‐node edge‐weighted graph and a subset of k terminal nodes,...
Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy
Online Speed Scaling Based on Active Job Count to Minimize Flow Plus Energy
2013,
This paper is concerned with online scheduling algorithms that aim at minimizing the...
Papers per page: