Keyword: combinatorial optimization

Found 3184 papers in total
Donation Center Location Problem
Donation Center Location Problem
2013,
We introduce and study the donation center location problem, which has an additional...
A Lower Bound of 1+f for Truthful Scheduling Mechanisms
A Lower Bound of 1+f for Truthful Scheduling Mechanisms
2013,
We study the mechanism design version of the unrelated machines scheduling problem,...
Mapping Simple Polygons: How Robots Benefit from Looking Back
Mapping Simple Polygons: How Robots Benefit from Looking Back
2013,
We consider the problem of mapping an initially unknown polygon of size n with a...
Exact and Parameterized Algorithms for Max Internal Spanning Tree
Exact and Parameterized Algorithms for Max Internal Spanning Tree
2013,
We consider the 𝒩𝒫 ‐hard problem of finding a spanning tree with a...
How to Use Spanning Trees to Navigate in Graphs
How to Use Spanning Trees to Navigate in Graphs
2013,
In this paper, we investigate three strategies of how to use a spanning tree T of a...
Efficient Coordination Mechanisms for Unrelated Machine Scheduling
Efficient Coordination Mechanisms for Unrelated Machine Scheduling
2013,
We present three new coordination mechanisms for scheduling n selfish jobs on m...
Recognizing d-Interval Graphs and d-Track Interval Graphs
Recognizing d-Interval Graphs and d-Track Interval Graphs
2013,
A d‐interval is the union of d disjoint intervals on the real line. A...
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...
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...
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 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...
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...
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...
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...
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...
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...
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...
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...
Papers per page: