Journal: Algorithmica

Found 758 papers in total
Improved Algorithms for Even Factors and Square‐Free Simple b‐Matchings
Improved Algorithms for Even Factors and Square‐Free Simple b‐Matchings
2012,
Given a digraph G =( VG , AG ), an even factor M ⊆ AG is a set formed by...
Exact Algorithms for Edge Domination
Exact Algorithms for Edge Domination
2012,
An edge dominating set in a graph G =( V , E ) is a subset of the edges D ⊆ E...
1‐Local 7/5‐Competitive Algorithm for Multicoloring Hexagonal Graphs
1‐Local 7/5‐Competitive Algorithm for Multicoloring Hexagonal Graphs
2012,
In the frequency allocation problem, we are given a cellular telephone network whose...
Theoretical Foundation for CMA‐ES from Information Geometry Perspective
Theoretical Foundation for CMA‐ES from Information Geometry Perspective
2012,
This paper explores the theoretical basis of the covariance matrix adaptation...
Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?
Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?
2012,
We study, from the perspective of competitive analysis, the trade‐off between...
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables
2012,
The sequential importance sampling (SIS) algorithm has gained considerable popularity...
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems
2012,
Ant Colony Optimization (ACO) is a popular optimization paradigm inspired by the...
Black‐Box Search by Unbiased Variation
Black‐Box Search by Unbiased Variation
2012,
The complexity theory for black‐box algorithms, introduced by Droste, Jansen,...
Multiplicative Drift Analysis
Multiplicative Drift Analysis
2012,
We introduce multiplicative drift analysis as a suitable way to analyze the runtime of...
3‐Colouring AT‐Free Graphs in Polynomial Time
3‐Colouring AT‐Free Graphs in Polynomial Time
2012,
Determining the complexity of the colouring problem on AT‐free graphs is one of...
Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning
Beyond Good Partition Shapes: An Analysis of Diffusive Graph Partitioning
2012,
In this paper we study the prevalent problem of graph partitioning by analyzing the...
On Independent Sets and Bicliques in Graphs
On Independent Sets and Bicliques in Graphs
2012,
Bicliques of graphs have been studied extensively, partially motivated by the large...
Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems
Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for Combinatorial Optimization Problems
2012,
We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a...
Property Testing on k‐Vertex‐Connectivity of Graphs
Property Testing on k‐Vertex‐Connectivity of Graphs
2012,
We present an algorithm for testing the k ‐vertex‐connectivity of graphs...
Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs
Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs
2012,
δ ‐Hyperbolic metric spaces have been defined by M. Gromov in 1987 via a...
Stackelberg Network Pricing Games
Stackelberg Network Pricing Games
2012,
We study a multi‐player one‐round game termed Stackelberg Network...
An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs
An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs
2012,
A graph is triconnected if it is connected, has at least 4 vertices and the removal of...
Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks
2012,
We consider the problem of dynamically reallocating (or re‐routing) m weighted...
Divide‐and‐Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
Divide‐and‐Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
2012,
The submodular system k ‐partition problem is a problem of partitioning a given...
Obtaining a Planar Graph by Vertex Deletion
Obtaining a Planar Graph by Vertex Deletion
2012,
In the k ‐ Apex problem the task is to find at most k vertices whose deletion...
Partitioning a Weighted Tree into Subtrees with Weights in a Given Range
Partitioning a Weighted Tree into Subtrees with Weights in a Given Range
2012,
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that...
Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees
Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees
2012,
Wilber’s logarithmic lower bound, concerning off‐line binary search tree...
Euclidean Prize‐Collecting Steiner Forest
Euclidean Prize‐Collecting Steiner Forest
2012,
In this paper, we consider Steiner forest and its generalizations,...
Approximation and Tidying–A Problem Kernel for s‐Plex Cluster Vertex Deletion
Approximation and Tidying–A Problem Kernel for s‐Plex Cluster Vertex Deletion
2012,
We introduce the NP‐hard graph‐based data clustering problem s ‐...
Papers per page: