Journal: Algorithmica

Found 758 papers in total
Minimum‐Perimeter Intersecting Polygons
Minimum‐Perimeter Intersecting Polygons
2012,
Given a set 𝒮 of segments in the plane, a polygon P is an intersecting polygon of...
Optimal Polygonal Representation of Planar Graphs
Optimal Polygonal Representation of Planar Graphs
2012,
In this paper, we consider the problem of representing planar graphs by polygons whose...
Lightweight Data Indexing and Compression in External Memory
Lightweight Data Indexing and Compression in External Memory
2012,
In this paper we describe algorithms for computing the Burrows‐Wheeler...
Sharp Separation and Applications to Exact and Parameterized Algorithms
Sharp Separation and Applications to Exact and Parameterized Algorithms
2012,
Many divide‐and‐conquer algorithms employ the fact that the vertex set...
Counting Hexagonal Patches and Independent Sets in Circle Graphs
Counting Hexagonal Patches and Independent Sets in Circle Graphs
2012,
A hexagonal patch is a plane graph in which inner faces have length 6, inner vertices...
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
2011,
Let G =( VG , AG ) be a digraph and let S ⊔ T be a bipartition of VG . A...
How to Guard a Graph?
How to Guard a Graph?
2011,
We initiate the study of the algorithmic foundations of games in which a set of cops...
Signature Theory in Holographic Algorithms
Signature Theory in Holographic Algorithms
2011,
In the theory of holographic algorithms proposed by Valiant, computation is expressed...
The Complexity of König Subgraph Problems and Above‐Guarantee Vertex Cover
The Complexity of König Subgraph Problems and Above‐Guarantee Vertex Cover
2011,
A graph is König‐Egerváry if the size of a minimum vertex cover...
Another Sub‐exponential Algorithm for the Simple Stochastic Game
Another Sub‐exponential Algorithm for the Simple Stochastic Game
2011,
We study the problem of solving simple stochastic games, and give both an interesting...
Faster Parameterized Algorithms for Minimum Fill‐in
Faster Parameterized Algorithms for Minimum Fill‐in
2011,
We present two parameterized algorithms for the Minimum Fill‐in problem, also...
A New Algorithm for Finding Trees with Many Leaves
A New Algorithm for Finding Trees with Many Leaves
2011,
We present an algorithm that finds out‐trees and out‐branchings with at...
Editing Graphs into Disjoint Unions of Dense Clusters
Editing Graphs into Disjoint Unions of Dense Clusters
2011,
In the Π‐ Cluster Editing problem, one is given an undirected graph G , a...
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs
2011,
Connected dominating set (CDS) in unit disk graphs has a wide range of applications in...
Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three
Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three
2011,
We characterize the planar straight line graphs ( Pslg s) that can be augmented to...
Exact Algorithms for the Bottleneck Steiner Tree Problem
Exact Algorithms for the Bottleneck Steiner Tree Problem
2011,
Given n points, called terminals, in the plane ℝ 2 and a positive integer k , the...
Extending Steinitz’s Theorem to Upward Star‐Shaped Polyhedra and Spherical Polyhedra
Extending Steinitz’s Theorem to Upward Star‐Shaped Polyhedra and Spherical Polyhedra
2011,
In 1922, Steinitz’s theorem gave a complete characterization of the topological...
An Improved Approximation Algorithm for the Traveling Tournament Problem
An Improved Approximation Algorithm for the Traveling Tournament Problem
2011,
This paper describes the traveling tournament problem, a well‐known benchmark...
Sleeping on the Job: Energy‐Efficient and Robust Broadcast for Radio Networks
Sleeping on the Job: Energy‐Efficient and Robust Broadcast for Radio Networks
2011,
We address the problem of minimizing power consumption when broadcasting a message...
Bounded Unpopularity Matchings
Bounded Unpopularity Matchings
2011,
We investigate the following problem: given a set of jobs and a set of people with...
Linear Time Algorithms for Generalized Edge Dominating Set Problems
Linear Time Algorithms for Generalized Edge Dominating Set Problems
2008,
We prove that a generalization of the edge dominating set problem, in which each edge...
The Cost of Cache‐Oblivious Searching
The Cost of Cache‐Oblivious Searching
2011,
This paper gives tight bounds on the cost of cache‐oblivious searching. The...
On Incentive Compatible Competitive Selection Protocols
On Incentive Compatible Competitive Selection Protocols
2011,
The problem of selecting m best players out of n candidates, through pairwise...
Topological Implications of Selfish Neighbor Selection in Unstructured Peer‐to‐Peer Networks
Topological Implications of Selfish Neighbor Selection in Unstructured Peer‐to‐Peer Networks
2011,
Current peer‐to‐peer (P2P) systems often suffer from a large fraction of...
Papers per page: