Journal: Algorithmica

Found 758 papers in total
On Dynamic Shortest Paths Problems
On Dynamic Shortest Paths Problems
2011,
We obtain the following results related to dynamic versions of the...
A Quadratic Algorithm for Finding Next‐to‐Shortest Paths in Graphs
A Quadratic Algorithm for Finding Next‐to‐Shortest Paths in Graphs
2011,
Given an edge‐weighted undirected graph G and two prescribed vertices u and v ,...
Quadratic Kernelization for Convex Recoloring of Trees
Quadratic Kernelization for Convex Recoloring of Trees
2011,
The Convex Recoloring (CR) problem measures how far a tree of characters differs from...
Approximation Algorithms for the Interval Constrained Coloring Problem
Approximation Algorithms for the Interval Constrained Coloring Problem
2011,
We consider the interval constrained coloring problem, which appears in the...
The Longest Path Problem has a Polynomial Solution on Interval Graphs
The Longest Path Problem has a Polynomial Solution on Interval Graphs
2011,
The longest path problem is the problem of finding a path of maximum length in a...
Energy‐Efficient Paths in Radio Networks
Energy‐Efficient Paths in Radio Networks
2011,
We consider a radio network consisting of n stations represented as the complete graph...
Graphical Congestion Games
Graphical Congestion Games
2011,
We consider congestion games with linear latency functions in which each player is...
Branch and Recharge: Exact Algorithms for Generalized Domination
Branch and Recharge: Exact Algorithms for Generalized Domination
2011,
In this paper we present branching algorithms for infinite classes of problems. The...
Reoptimization of the Shortest Common Superstring Problem
Reoptimization of the Shortest Common Superstring Problem
2011,
A reoptimization problem describes the following scenario: given an instance of an...
Minimum Weight Convex Steiner Partitions
Minimum Weight Convex Steiner Partitions
2011,
New tight bounds are presented on the minimum length of planar straight line graphs...
Constructing the Simplest Possible Phylogenetic Network from Triplets
Constructing the Simplest Possible Phylogenetic Network from Triplets
2011,
A phylogenetic network is a directed acyclic graph that visualizes an evolutionary...
Location‐Oblivious Distributed Unit Disk Graph Coloring
Location‐Oblivious Distributed Unit Disk Graph Coloring
2011,
We present the first location-oblivious distributed unit disk graph coloring algorithm...
Capacitated Domination Problem
Capacitated Domination Problem
2011,
We consider a generalization of the well‐known domination problem on graphs....
An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times
An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times
2011,
We address the problem of sequential single machine scheduling of jobs with release...
Exact Algorithms for Cluster Editing: Evaluation and Experiments
Exact Algorithms for Cluster Editing: Evaluation and Experiments
2011,
The Cluster Editing problem is defined as follows: Given an undirected, loopless...
Crossing Numbers of Graphs with Rotation Systems
Crossing Numbers of Graphs with Rotation Systems
2011,
We show that computing the crossing number and the odd crossing number of a graph with...
Selfish Bin Packing
Selfish Bin Packing
2011,
Following recent interest in the study of computer science problems in a game...
Approximability of Packing Disjoint Cycles
Approximability of Packing Disjoint Cycles
2011,
Given a graph G , the edge‐disjoint cycle packing problem is to find the...
Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems
Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems
2011,
Following in the spirit of data structure and algorithm correctness checking,...
Crossing Number and Weighted Crossing Number of Near‐Planar Graphs
Crossing Number and Weighted Crossing Number of Near‐Planar Graphs
2011,
A nonplanar graph G is near‐planar if it contains an edge e such that G - e is...
Improved Approximations for Guarding 1.5‐Dimensional Terrains
Improved Approximations for Guarding 1.5‐Dimensional Terrains
2011,
We present a 4-approximation algorithm for the problem of placing the fewest guards on...
On Centralized Smooth Scheduling
On Centralized Smooth Scheduling
2011,
This paper studies evenly distributed sets of natural numbers and their applications...
Injective Colorings of Graphs with Low Average Degree
Injective Colorings of Graphs with Low Average Degree
2011,
Let mad( G ) denote the maximum average degree (over all subgraphs) of G and let χ...
On the Planarization of Wireless Sensor Networks
On the Planarization of Wireless Sensor Networks
2011,
Network planarization has been an important technique in numerous sensornet...
Papers per page: