Journal: Algorithmica

Found 758 papers in total
Primal‐Dual Algorithms for Precedence Constrained Covering Problems
Primal‐Dual Algorithms for Precedence Constrained Covering Problems
2017,
A covering problem is an integer linear program of type min { c T x ∣ A x ≥ D ,...
Resolving Braess’s Paradox in Random Networks
Resolving Braess’s Paradox in Random Networks
2017,
Braess’s paradox states that removing a part of a network may improve the...
Online Packet-Routing in Grids with Bounded Buffers
Online Packet-Routing in Grids with Bounded Buffers
2017,
We present deterministic and randomized algorithms for the problem of online packet...
Robustness of the Rotor‐Router Mechanism
Robustness of the Rotor‐Router Mechanism
2017,
The rotor–router model , also called the Propp machine , was first considered as...
On Computing an Optimal Semi-matching
On Computing an Optimal Semi-matching
2017,
A semi‐matching in a bipartite graph G = ( U , V , E ) is a set of edges M...
Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
2017,
We consider the problems of finding optimal identifying codes, (open)...
Extending Partial Representations of Interval Graphs
Extending Partial Representations of Interval Graphs
2017,
Interval graphs are intersection graphs of closed intervals of the real‐line....
Asynchronous Rumor Spreading on Random Graphs
Asynchronous Rumor Spreading on Random Graphs
2017,
We perform a thorough study of various characteristics of the asynchronous...
Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT
Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT
2017,
We present several sparsification lower and upper bounds for classic problems in graph...
Connectivity Graphs of Uncertainty Regions
Connectivity Graphs of Uncertainty Regions
2017,
We study connectivity relations among points, where the precise location of each input...
Improved Algorithms for Distributed Entropy Monitoring
Improved Algorithms for Distributed Entropy Monitoring
2017,
Modern data management systems often need to deal with massive, dynamic and inherently...
Stable Matching with Network Externalities
Stable Matching with Network Externalities
2017,
We study the stable roommates problem in networks where players are embedded in a...
On the Approximability of Digraph Ordering
On the Approximability of Digraph Ordering
2017,
Given an n ‐vertex digraph D = ( V , A ) the Max ‐ k ‐ Ordering...
Strong ETH and Resolution via Games and the Multiplicity of Strategies
Strong ETH and Resolution via Games and the Multiplicity of Strategies
2017,
We consider a proof system intermediate between regular Resolution, in which no...
Parameterized Complexity of Sparse Linear Complementarity Problems
Parameterized Complexity of Sparse Linear Complementarity Problems
2017,
In this paper, we study the parameterized complexity of the linear complementarity...
Matroid and Knapsack Center Problems
Matroid and Knapsack Center Problems
2016,
In the classic k ‐center problem, we are given a metric graph, and the...
Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
2016,
Although widely applied in optimisation, relatively little has been proven rigorously...
AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations
AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations
2016,
Drucker (Proceedings of the 53rd annual symposium on foundations of computer science...
New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
New Approximation Algorithms for the Unsplittable Capacitated Facility Location Problem
2016,
In this paper, we consider the Unsplittable (hard) Capacitated Facility Location...
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
2016,
The NP ‐complete Permutation Pattern Matching problem asks whether a k...
Chordal Editing is Fixed-Parameter Tractable
Chordal Editing is Fixed-Parameter Tractable
2016,
Graph modification problems are typically asked as follows: is there a small set of...
Computing Directed Pathwidth in O(1.89n) Time
Computing Directed Pathwidth in O(1.89n) Time
2016,
We give an algorithm for computing the directed pathwidth of a digraph with n vertices...
Two-Page Book Embeddings of 4-Planar Graphs
Two-Page Book Embeddings of 4-Planar Graphs
2016,
Back in the eighties, Heath [Algorithms for embedding graphs in books. PhD thesis,...
The Impact of Random Initialization on the Runtime of Randomized Search Heuristics
The Impact of Random Initialization on the Runtime of Randomized Search Heuristics
2016,
Analyzing the runtime of a Randomized Search Heuristic (RSH) by theoretical means...
Papers per page: