Journal: Algorithmica

Found 758 papers in total
Inequalities for the Number of Walks in Graphs
Inequalities for the Number of Walks in Graphs
2013,
We investigate the growth of the number w k of walks of length k in undirected graphs...
External-Memory Multimaps
External-Memory Multimaps
2013,
Many data structures support dictionaries, also known as maps or associative arrays,...
Approximately Uniform Online Checkpointing with Bounded Memory
Approximately Uniform Online Checkpointing with Bounded Memory
2013,
In many complex computational processes one may want to store a sample of the...
Compressed Directed Acyclic Word Graph with Application in Local Alignment
Compressed Directed Acyclic Word Graph with Application in Local Alignment
2013,
Suffix tree, suffix array, and directed acyclic word graph (DAWG) are...
On Total Unimodularity of Edge‐Edge Adjacency Matrices
On Total Unimodularity of Edge‐Edge Adjacency Matrices
2013,
We consider total unimodularity for edge–edge adjacency matrices that represent...
Online Clustering with Variable Sized Clusters
Online Clustering with Variable Sized Clusters
2013,
Online clustering problems are problems where the classification of points into sets...
Cleaning Interval Graphs
Cleaning Interval Graphs
2013,
We investigate a special case of the Induced Subgraph Isomorphism problem, where both...
Route-Enabling Graph Orientation Problems
Route-Enabling Graph Orientation Problems
2013,
Given an undirected and edge‐weighted graph G together with a set of ordered...
I/O Efficient Dynamic Data Structures for Longest Prefix Queries
I/O Efficient Dynamic Data Structures for Longest Prefix Queries
2013,
We present an efficient data structure for finding the longest prefix of a query...
Two-stage Robust Network Design with Exponential Scenarios
Two-stage Robust Network Design with Exponential Scenarios
2013,
We study two‐stage robust variants of combinatorial optimization problems on...
Streaming Graph Computations with a Helpful Advisor
Streaming Graph Computations with a Helpful Advisor
2013,
Motivated by the trend to outsource work to commercial cloud computing services, we...
Power Domination in Circular-Arc Graphs
Power Domination in Circular-Arc Graphs
2013,
A set S ⊆ V is a power dominating set (PDS) of a graph G =( V , E ) if every...
A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
2013,
Given an undirected graph G =( V , E ) with positive edge lengths and two vertices s...
Thresholds for Extreme Orientability
Thresholds for Extreme Orientability
2014,
Multiple‐choice load balancing has been a topic of intense study since the...
Practical and Efficient Split Decomposition via Graph-Labelled Trees
Practical and Efficient Split Decomposition via Graph-Labelled Trees
2014,
Split decomposition of graphs was introduced by Cunningham (under the name join...
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
2014,
We reconsider the well‐studied Selfish Routing game with affine latency...
On the Huffman and Alphabetic Tree Problem with General Cost Functions
On the Huffman and Alphabetic Tree Problem with General Cost Functions
2014,
We address generalized versions of the Huffman and Alphabetic Tree Problem where the...
An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function
An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function
2014,
The Lovász ϑ ‐function (Lovász in IEEE Trans. Inf....
Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor
Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor
2014,
We consider the construction of sparse covers for planar graphs and other graphs that...
Improved Algorithms for Partial Curve Matching
Improved Algorithms for Partial Curve Matching
2014,
We revisit the problem of deciding whether a given curve resembles some part of a...
Inclusion/Exclusion Meets Measure and Conquer
Inclusion/Exclusion Meets Measure and Conquer
2014,
Inclusion/exclusion and measure and conquer are two central techniques from the field...
On the Advantage of Overlapping Clusters for Minimizing Conductance
On the Advantage of Overlapping Clusters for Minimizing Conductance
2014,
Graph clustering is an important problem with applications to bioinformatics,...
Cache-Oblivious Hashing
Cache-Oblivious Hashing
2014,
The hash table, especially its external memory version, is one of the most important...
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs
2014,
A spanning tree T of a graph G is called a tree t ‐ spanner of G if the...
Papers per page: