Journal: Algorithmica

Found 758 papers in total
Approximate Guarding of Monotone and Rectilinear Polygons
Approximate Guarding of Monotone and Rectilinear Polygons
2013,
We show that vertex guarding a monotone polygon is NP‐hard and construct a...
Median Trajectories
Median Trajectories
2013,
We investigate the concept of a median among a set of trajectories. We establish...
Improved Algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs
Improved Algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs
2013,
We consider a common scenario in competitive location, where two competitors...
On Finding Min-Min Disjoint Paths
On Finding Min-Min Disjoint Paths
2013,
The Min‐Min problem of finding a disjoint‐path pair with the length of...
A Linear Time Algorithm for L(2,1)-Labeling of Trees
A Linear Time Algorithm for L(2,1)-Labeling of Trees
2013,
An L (2,1)‐labeling of a graph G is an assignment f from the vertex set V ( G )...
Approximating Points by a Piecewise Linear Function
Approximating Points by a Piecewise Linear Function
2013,
Approximating points by piecewise linear functions is an intensively researched topic...
Relaxed Spanners for Directed Disk Graphs
Relaxed Spanners for Directed Disk Graphs
2013,
Let ( V , δ ) be a finite metric space, where V is a set of n points and δ...
Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets
Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets
2013,
Phylogenetic networks are a generalization of phylogenetic trees that are used in...
Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix
Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix
2013,
Given a matrix A ∈ℝ m × n ( n vectors in m dimensions), and a positive...
The Longest Path Problem Is Polynomial on Cocomparability Graphs
The Longest Path Problem Is Polynomial on Cocomparability Graphs
2013,
The longest path problem is the problem of finding a path of maximum length in a...
Optimal Tracking of Distributed Heavy Hitters and Quantiles
Optimal Tracking of Distributed Heavy Hitters and Quantiles
2013,
We consider the problem of tracking heavy hitters and quantiles in the distributed...
The Parallel Complexity of Graph Canonization Under Abelian Group Action
The Parallel Complexity of Graph Canonization Under Abelian Group Action
2013,
We study the problem of computing canonical forms for graphs and hypergraphs under...
The Parameterized Complexity of Local Search for TSP, More Refined
The Parameterized Complexity of Local Search for TSP, More Refined
2013,
We extend previous work on the parameterized complexity of local search for the...
On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
2013,
For a graph G =( V , E ) and a color set C , let f : E → C be an...
Self-Assembling Rulers for Approximating Generalized Sierpinski Carpets
Self-Assembling Rulers for Approximating Generalized Sierpinski Carpets
2013,
Discrete self‐similar fractals have been used as test cases for...
FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time
FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time
2013,
In computational phylogenetics, supertree methods provide a way to reconstruct larger...
Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions
Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions
2013,
A random geometric graph (RGG) is defined by placing n points uniformly at random in...
The School Bus Problem on Trees
The School Bus Problem on Trees
2013,
The School Bus Problem is an NP‐hard vehicle routing problem in which the goal...
Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction
Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction
2013,
The compaction problem is to partition the vertices of an input graph G onto the...
Asymptotic Enumeration of Extensional Acyclic Digraphs
Asymptotic Enumeration of Extensional Acyclic Digraphs
2013,
The enumeration of extensional acyclic digraphs, which have the property that the...
Analysis of the ‘Hiring Above the Median’ Selection Strategy for the Hiring Problem
Analysis of the ‘Hiring Above the Median’ Selection Strategy for the Hiring Problem
2013,
This paper gives a precise mathematical analysis of the behaviour of ‘hiring...
A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps
A Central Limit Theorem for the Number of Degree-k Vertices in Random Maps
2013,
We prove that the number of vertices of given degree in (general or...
Message Passing Algorithms for MLS-3LIN Problem
Message Passing Algorithms for MLS-3LIN Problem
2013,
MLS‐3LIN problem is a problem of finding a most likely solution for a given...
Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations
Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations
2013,
In a proportional contact representation of a planar graph, each vertex is represented...
Papers per page: