Journal: Algorithmica

Found 758 papers in total
Set It and Forget It: Approximating the Set Once Strip Cover Problem
Set It and Forget It: Approximating the Set Once Strip Cover Problem
2017,
We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed...
Full-Fledged Real-Time Indexing for Constant Size Alphabets
Full-Fledged Real-Time Indexing for Constant Size Alphabets
2017,
In this paper we describe a data structure that supports pattern matching queries on a...
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
2017,
Fan‐planar graphs were recently introduced as a generalization of 1‐...
The Book Thickness of 1-Planar Graphs is Constant
The Book Thickness of 1-Planar Graphs is Constant
2017,
In a book embedding, the vertices of a graph are placed on the ‘spine’ of...
Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs
Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs
2017,
Depth First Search (DFS) tree is a fundamental data structure for graphs used in...
Efficient Sampling Methods for Discrete Distributions
Efficient Sampling Methods for Discrete Distributions
2017,
We study the fundamental problem of the exact and efficient generation of random...
Optimal Parallel Quantum Query Algorithms
Optimal Parallel Quantum Query Algorithms
2017,
We study the complexity of quantum query algorithms that make p queries in parallel in...
Building Efficient and Compact Data Structures for Simplicial Complexes
Building Efficient and Compact Data Structures for Simplicial Complexes
2017,
The Simplex Tree (ST) is a recently introduced data structure that can represent...
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-Off Schedules
2017,
We give a polynomial time algorithm to compute an optimal energy and fractional...
On the Value of Job Migration in Online Makespan Minimization
On the Value of Job Migration in Online Makespan Minimization
2017,
Makespan minimization on identical parallel machines is a classical scheduling...
On Kernelization and Approximation for the Vector Connectivity Problem
On Kernelization and Approximation for the Vector Connectivity Problem
2017,
In the Vector Connectivity problem we are given an undirected graph G = ( V , E ) , a...
Fixed-Parameter Tractable Distances to Sparse Graph Classes
Fixed-Parameter Tractable Distances to Sparse Graph Classes
2017,
We show that for various classes C of sparse graphs, and several measures of distance...
Linear Kernels for Outbranching Problems in Sparse Digraphs
Linear Kernels for Outbranching Problems in Sparse Digraphs
2017,
In the k ‐ Leaf Out‐Branching and k ‐ Internal...
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
2017,
In the Steiner Tree problem one is given an undirected graph, a subset T of its...
Scheduling with Deadlines and Buffer Management with Processing Requirements
Scheduling with Deadlines and Buffer Management with Processing Requirements
2017,
We discuss the well known online job scheduling problem with release times and...
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
2017,
Given an undirected, edge‐weighted graph G together with pairs of vertices,...
Parameterized and Approximation Algorithms for the Load Coloring Problem
Parameterized and Approximation Algorithms for the Load Coloring Problem
2017,
Let c , k be two positive integers. Given a graph G = ( V , E ) , the c ‐ Load...
How to Sort by Walking and Swapping on Paths and Trees
How to Sort by Walking and Swapping on Paths and Trees
2017,
Consider a graph G with n vertices. On each vertex we place a box. The n vertices and...
Improved Analysis of Complete-Linkage Clustering
Improved Analysis of Complete-Linkage Clustering
2017,
Complete‐linkage clustering is a very popular method for computing hierarchical...
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem
An Experimental Evaluation of the Best-of-Many Christofides’ Algorithm for the Traveling Salesman Problem
2017,
Recent papers on approximation algorithms for the traveling salesman problem (TSP)...
Complexity and Approximability of Parameterized MAX-CSPs
Complexity and Approximability of Parameterized MAX-CSPs
2017,
We study the optimization version of constraint satisfaction problems...
A Polynomial Kernel for Block Graph Deletion
A Polynomial Kernel for Block Graph Deletion
2017,
In the Block Graph Deletion problem, we are given a graph G on n vertices and a...
Quick but Odd Growth of Cacti
Quick but Odd Growth of Cacti
2017,
Let F be a family of graphs. Given an n ‐vertex input graph G and a positive...
FPTAS for Minimizing the Earth Mover’s Distance Under Rigid Transformations and Related Problems
FPTAS for Minimizing the Earth Mover’s Distance Under Rigid Transformations and Related Problems
2017,
In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth...
Papers per page: