Journal: Algorithmica

Found 758 papers in total
Faster Swap Edge Computation in Minimum Diameter Spanning Trees
Faster Swap Edge Computation in Minimum Diameter Spanning Trees
2012,
In network communication systems, frequently messages are routed along a minimum...
Construction Sequences and Certifying 3‐connectivity
Construction Sequences and Certifying 3‐connectivity
2012,
Tutte proved that every 3‐vertex‐connected graph G on more than 4...
Fast Arc‐Annotated Subsequence Matching in Linear Space
Fast Arc‐Annotated Subsequence Matching in Linear Space
2012,
An arc‐annotated string is a string of characters, called bases, augmented with...
Succinct Representation of Labeled Graphs
Succinct Representation of Labeled Graphs
2012,
In many applications, the properties of an object being modeled are stored as labels...
Mapping Filtering Streaming Applications
Mapping Filtering Streaming Applications
2012,
In this paper, we explore the complexity of mapping filtering streaming applications...
Drawing (Complete) Binary Tanglegrams
Drawing (Complete) Binary Tanglegrams
2012,
A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are...
Competitive Weighted Matching in Transversal Matroids
Competitive Weighted Matching in Transversal Matroids
2012,
Consider a bipartite graph with a set of left‐vertices and a set of...
A Scheme for Computing Minimum Covers within Simple Regions
A Scheme for Computing Minimum Covers within Simple Regions
2012,
Let X be a simple region (e.g., a simple polygon), and let Q be a set of points in X ....
Many Distances in Planar Graphs
Many Distances in Planar Graphs
2012,
We show how to compute in O ( n 4/3 log 1/3 n + n 2/3 k 2/3 log n ) time the...
Fast Algorithms for max independent set
Fast Algorithms for max independent set
2012,
We first propose a method, called ‘bottom‐up method’ that,...
Shortest Paths in Time‐Dependent FIFO Networks
Shortest Paths in Time‐Dependent FIFO Networks
2012,
In this paper, we study the time‐dependent shortest paths problem for two types...
Pruning 2‐Connected Graphs
Pruning 2‐Connected Graphs
2012,
Given an undirected graph G with edge costs and a specified set of terminals, let the...
Aligning Two Convex Figures to Minimize Area or Perimeter
Aligning Two Convex Figures to Minimize Area or Perimeter
2012,
Given two compact convex sets P and Q in the plane, we consider the problem of finding...
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil‐2 Groups
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil‐2 Groups
2012,
In this paper we show that the hidden subgroup problem in nil‐2 groups, that is...
The k‐in‐a‐Path Problem for Claw‐free Graphs
The k‐in‐a‐Path Problem for Claw‐free Graphs
2012,
The k ‐ in‐a‐Path problem is to test whether a graph contains an...
Approximability of the Firefighter Problem
Approximability of the Firefighter Problem
2012,
We provide approximation algorithms for several variants of the Firefighter problem on...
Finding Induced Paths of Given Parity in Claw‐Free Graphs
Finding Induced Paths of Given Parity in Claw‐Free Graphs
2012,
The Parity Path problem is to decide if a given graph contains both an induced path of...
The Parameterized Complexity of Stabbing Rectangles
The Parameterized Complexity of Stabbing Rectangles
2012,
The NP‐complete geometric covering problem Rectangle Stabbing is defined as...
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
2012,
Set agreement is a fundamental problem in distributed computing in which processes...
Denesting by Bounded Degree Radicals
Denesting by Bounded Degree Radicals
2000,
Given a nested radical α involving only d th roots, we show how to compute an...
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs
A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs
2000,
Given a graph G=(V,E) and two vertices s,t ∈V , s eq t , the Menger problem is to...
Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes
Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes
2000,
We consider broadcasting among n processors, f of which can be faulty. A...
Partitioning Planar Graphs with Vertex Costs: Algorithms and Applications
Partitioning Planar Graphs with Vertex Costs: Algorithms and Applications
2000,
We prove separator theorems in which the size of the separator is minimized with...
Dynamically Switching Vertices in Planar Graphs
Dynamically Switching Vertices in Planar Graphs
2000,
We consider graphs whose vertices may be in one of two different states: either on or...
Papers per page: