Journal: Algorithmica

Found 758 papers in total
Stochastic Budget Optimization in Internet Advertising
Stochastic Budget Optimization in Internet Advertising
2013,
Internet advertising is a sophisticated game in which the many advertisers...
Succinct 2D Dictionary Matching
Succinct 2D Dictionary Matching
2013,
The dictionary matching problem seeks all locations in a given text that match any of...
Sublinear Algorithms for Approximating String Compressibility
Sublinear Algorithms for Approximating String Compressibility
2013,
We raise the question of approximating the compressibility of a string with respect to...
On the (Non-)Existence of Polynomial Kernels for Pl-Free Edge Modification Problems
On the (Non-)Existence of Polynomial Kernels for Pl-Free Edge Modification Problems
2013,
Given a graph G =( V , E ) and a positive integer k , an edge modification problem for...
Fast Polynomial-Space Algorithms Using Inclusion-Exclusion
Fast Polynomial-Space Algorithms Using Inclusion-Exclusion
2013,
Given a graph with n vertices, k terminals and positive integer weights not larger...
A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold Topology
A Tree Traversal Algorithm for Decision Problems in Knot Theory and 3-Manifold Topology
2013,
In low‐dimensional topology, many important decision algorithms are based on...
Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem
2013,
In this paper, we consider multi‐objective evolutionary algorithms for the...
Proper Interval Vertex Deletion
Proper Interval Vertex Deletion
2013,
The NP‐complete problem Proper Interval Vertex Deletion is to decide whether an...
Small Vertex Cover makes Petri Net Coverability and Boundedness Easier
Small Vertex Cover makes Petri Net Coverability and Boundedness Easier
2013,
The coverability and boundedness problems for Petri nets are known to be Expspace...
Tile Complexity of Approximate Squares
Tile Complexity of Approximate Squares
2013,
The standard Tile Assembly Model (TAM) of Winfree (Algorithmic self‐assembly of...
Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs
Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs
2013,
Let G =( V , E ) be an undirected unweighted graph. A path between any two vertices u...
Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks
Engineering a New Algorithm for Distributed Shortest Paths on Dynamic Networks
2013,
We study the problem of dynamically updating all‐pairs shortest paths in a...
Maximum Matching in Regular and Almost Regular Graphs
Maximum Matching in Regular and Almost Regular Graphs
2013,
We present an O ( n 2 log n )‐time algorithm that finds a maximum matching in a...
Isotonic Regression via Partitioning
Isotonic Regression via Partitioning
2013,
Algorithms are given for determining weighted isotonic regressions satisfying order...
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Greedy Δ-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
2013,
This paper describes a simple greedy Δ ‐approximation algorithm for any...
Negative Interactions in Irreversible Self-assembly
Negative Interactions in Irreversible Self-assembly
2013,
This paper explores the use of negative (i.e., repulsive) interactions in the abstract...
Fast Maximal Cliques Enumeration in Sparse Graphs
Fast Maximal Cliques Enumeration in Sparse Graphs
2013,
In this paper, we consider the problem of generating all maximal cliques in a sparse...
Donation Center Location Problem
Donation Center Location Problem
2013,
We introduce and study the donation center location problem, which has an additional...
A Lower Bound of 1+f for Truthful Scheduling Mechanisms
A Lower Bound of 1+f for Truthful Scheduling Mechanisms
2013,
We study the mechanism design version of the unrelated machines scheduling problem,...
Mapping Simple Polygons: How Robots Benefit from Looking Back
Mapping Simple Polygons: How Robots Benefit from Looking Back
2013,
We consider the problem of mapping an initially unknown polygon of size n with a...
Exact and Parameterized Algorithms for Max Internal Spanning Tree
Exact and Parameterized Algorithms for Max Internal Spanning Tree
2013,
We consider the 𝒩𝒫 ‐hard problem of finding a spanning tree with a...
How to Use Spanning Trees to Navigate in Graphs
How to Use Spanning Trees to Navigate in Graphs
2013,
In this paper, we investigate three strategies of how to use a spanning tree T of a...
Efficient Coordination Mechanisms for Unrelated Machine Scheduling
Efficient Coordination Mechanisms for Unrelated Machine Scheduling
2013,
We present three new coordination mechanisms for scheduling n selfish jobs on m...
Recognizing d-Interval Graphs and d-Track Interval Graphs
Recognizing d-Interval Graphs and d-Track Interval Graphs
2013,
A d‐interval is the union of d disjoint intervals on the real line. A...
Papers per page: