Journal: Algorithmica

Found 758 papers in total
The Parameterized Complexity of Geometric Graph Isomorphism
The Parameterized Complexity of Geometric Graph Isomorphism
2016,
We study the parameterized complexity of Geometric Graph Isomorphism (Known as the...
Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems
Superpolynomial Lower Bounds for the (1+1) EA on Some Easy Combinatorial Problems
2016,
The ( 1 + 1 ) EA is a simple evolutionary algorithm that is known to be efficient...
Between Treewidth and Clique-Width
Between Treewidth and Clique-Width
2016,
Many hard graph problems can be solved efficiently when restricted to graphs of...
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
2016,
A commonly studied means of parameterizing graph problems is the deletion distance...
Concentration of First Hitting Times Under Additive Drift
Concentration of First Hitting Times Under Additive Drift
2016,
Recent advances in drift analysis have given us better and better tools for...
Separation Dimension of Graphs and Hypergraphs
Separation Dimension of Graphs and Hypergraphs
2016,
Separation dimension of a hypergraph H , denoted by π ( H ) , is the smallest...
On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth
On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth
2016,
In this paper we prove a space lower bound of n Ω ( k ) for...
Robustness of Populations in Stochastic Environments
Robustness of Populations in Stochastic Environments
2016,
We consider stochastic versions of OneMax and LeadingOnes and analyze the performance...
A Parameterized Study of Maximum Generalized Pattern Matching Problems
A Parameterized Study of Maximum Generalized Pattern Matching Problems
2016,
The generalized function matching (GFM) problem has been intensively studied starting...
Finding Shortest Paths Between Graph Colourings
Finding Shortest Paths Between Graph Colourings
2016,
The k ‐colouring reconfiguration problem asks whether, for a given graph G ,...
Solving Linear Equations Parameterized by Hamming Weight
Solving Linear Equations Parameterized by Hamming Weight
2016,
Given a system of linear equations A x = b over the binary field ‐ F 2 and an...
MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions
MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions
2016,
We study the behavior of a population‐based EA and the Max–Min Ant System...
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem
2016,
The workflow satisfiability problem ( wsp ) is a problem of practical interest that...
A New Characterization of Pk -Free Graphs
A New Characterization of Pk -Free Graphs
2016,
Let G be a connected P k ‐free graph, k ≥ 4 . We show that G admits a...
The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments
The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments
2016,
We study the exponential time complexity of approximate counting satisfying...
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
2015,
We study the problem of finding small s – t separators that induce graphs having...
An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem
An Improved Approximation Algorithm for the Minimum Cost Subset k-Connected Subgraph Problem
2015,
The minimum cost subset k ‐connected subgraph problem is a cornerstone problem...
Max-Cut Parameterized Above the Edwards-Erdos Bound
Max-Cut Parameterized Above the Edwards-Erdos Bound
2015,
We study the boundary of tractability for the Max‐Cut problem in graphs. Our...
k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
2015,
Cops and robber games , introduced by Winkler and Nowakowski (in Discrete Math....
A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
2015,
We give a subexponential fixed parameter algorithm for one‐sided crossing...
Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error
Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error
2015,
In this paper we are interested in indexing texts for substring matching queries with...
Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions
Parameterized Algorithms for the 2-Clustering Problem with Minimum Sum and Minimum Sum of Squares Objective Functions
2015,
In the Min‐Sum 2‐Clustering problem, we are given a graph and a...
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets
An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets
2015,
We show that all minimal edge dominating sets of a graph can be generated in...
D2-Tree: A New Overlay with Deterministic Bounds
D2-Tree: A New Overlay with Deterministic Bounds
2015,
We present a new overlay, called the Deterministic Decentralized tree ( D 2...
Papers per page: