Journal: Algorithmica

Found 758 papers in total
Optimal Indexes for Sparse Bit Vectors
Optimal Indexes for Sparse Bit Vectors
2014,
We consider the problem of supporting rank and select operations on a bit vector of...
Computing the Throughput of Probabilistic and Replicated Streaming Applications
Computing the Throughput of Probabilistic and Replicated Streaming Applications
2014,
In this paper, we investigate how to compute the throughput of probabilistic and...
Multikey Quickselect
Multikey Quickselect
2014,
We present multikey quickselect: an efficient, in‐place,...
Better Size Estimation for Sparse Matrix Products
Better Size Estimation for Sparse Matrix Products
2014,
We consider the problem of doing fast and reliable estimation of the number z of...
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy
2014,
Tolerance graphs model interval relations in such a way that intervals can tolerate a...
Practical and Efficient Circle Graph Recognition
Practical and Efficient Circle Graph Recognition
2014,
Circle graphs are the intersection graphs of chords in a circle. This paper presents...
Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes
Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes
2014,
We show that the following fundamental edge‐colouring problem can be solved in...
Collecting Weighted Items from a Dynamic Queue
Collecting Weighted Items from a Dynamic Queue
2013,
We consider online competitive algorithms for the problem of collecting weighted items...
Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs
2013,
The Hamiltonian Cycle problem is the problem of deciding whether an n ‐vertex...
Adaptive Drift Analysis
Adaptive Drift Analysis
2013,
We show that, for any c >0, the (1+1) evolutionary algorithm using an...
A Cubic‐Vertex Kernel for Flip Consensus Tree
A Cubic‐Vertex Kernel for Flip Consensus Tree
2014,
Given a bipartite graph G =( V c , V t , E ) and a nonnegative integer k , the...
A Uniform Paradigm to Succinctly Encode Various Families of Trees
A Uniform Paradigm to Succinctly Encode Various Families of Trees
2014,
We propose a uniform method to encode various types of trees succinctly. These...
Algorithms for Placing Monitors in a Flow Network
Algorithms for Placing Monitors in a Flow Network
2014,
In the Flow Edge‐Monitor Problem, we are given an undirected graph G =( V , E...
Parameterized Complexity of Eulerian Deletion Problems
Parameterized Complexity of Eulerian Deletion Problems
2014,
We study a family of problems where the goal is to make a graph Eulerian, i.e.,...
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines
Graph Balancing: A Special Case of Scheduling Unrelated Parallel Machines
2014,
We design a 1.75‐approximation algorithm for a special case of scheduling...
Online Metric Tracking and Smoothing
Online Metric Tracking and Smoothing
2014,
We consider the online smoothing problem , in which a tracker is required to maintain...
Contracting Graphs to Paths and Trees
Contracting Graphs to Paths and Trees
2014,
Vertex deletion and edge deletion problems play a central role in parameterized...
Conflict‐Free Chromatic Art Gallery Coverage
Conflict‐Free Chromatic Art Gallery Coverage
2014,
We consider a chromatic variant of the art gallery problem, where each guard is...
Evolutionary Algorithms for Quantum Computers
Evolutionary Algorithms for Quantum Computers
2014,
In this article, we formulate and study quantum analogues of randomized search...
Worst Case and Probabilistic Analysis of the 2‐Opt Algorithm for the TSP
Worst Case and Probabilistic Analysis of the 2‐Opt Algorithm for the TSP
2014,
2‐Opt is probably the most basic local search heuristic for the TSP. This...
Identifying Shapes Using Self‐assembly
Identifying Shapes Using Self‐assembly
2012,
In this paper, we introduce the following problem in the theory of algorithmic...
Minimum Cost Partitions of Trees with Supply and Demand
Minimum Cost Partitions of Trees with Supply and Demand
2012,
Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex,...
From Holant to #CSP and Back: Dichotomy for Holantc Problems
From Holant to #CSP and Back: Dichotomy for Holantc Problems
2012,
We explore the intricate interdependent relationship among counting problems,...
Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
2012,
For graph G , let bw( G ) denote the branchwidth of G and gm( G ) the largest integer...
Papers per page: