Found 97029 papers in total
On Kernelization and Approximation for the Vector Connectivity Problem
2017,
In the Vector Connectivity problem we are given an undirected graph G = ( V , E ) , a demand function...
Fixed-Parameter Tractable Distances to Sparse Graph Classes
2017,
We show that for various classes C of sparse graphs, and several measures of distance to such classes...
Linear Kernels for Outbranching Problems in Sparse Digraphs
2017,
In the k ‐ Leaf Out‐Branching and k ‐ Internal Out‐Branching problems we are...
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices
2017,
In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k...
Scheduling with Deadlines and Buffer Management with Processing Requirements
2017,
We discuss the well known online job scheduling problem with release times and deadlines, alongside an...
Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
2017,
Given an undirected, edge‐weighted graph G together with pairs of vertices, called pairs of...
Parameterized and Approximation Algorithms for the Load Coloring Problem
2017,
Let c , k be two positive integers. Given a graph G = ( V , E ) , the c ‐ Load Coloring problem...
Robust optimal investment and reinsurance problem for a general insurance company under Heston model
2017,
In this paper, we study a robust optimal investment and reinsurance problem for a general insurance...
FPTAS for Minimizing the Earth Mover’s Distance Under Rigid Transformations and Related Problems
2017,
In this paper, we consider the problem (denoted as EMDRT) of minimizing the earth mover’s distance...
Primal‐Dual Algorithms for Precedence Constrained Covering Problems
2017,
A covering problem is an integer linear program of type min { c T x ∣ A x ≥ D , 0 ≤ x ≤ d , x...
Resolving Braess’s Paradox in Random Networks
2017,
Braess’s paradox states that removing a part of a network may improve the players’ latency at...
Online Packet-Routing in Grids with Bounded Buffers
2017,
We present deterministic and randomized algorithms for the problem of online packet routing in grids in...
Robustness of the Rotor‐Router Mechanism
2017,
The rotor–router model , also called the Propp machine , was first considered as a deterministic...
On Computing an Optimal Semi-matching
2017,
A semi‐matching in a bipartite graph G = ( U , V , E ) is a set of edges M ⊆ E such that each...
Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
2017,
We consider the problems of finding optimal identifying codes, (open) locating‐dominating sets and...
Extending Partial Representations of Interval Graphs
2017,
Interval graphs are intersection graphs of closed intervals of the real‐line. The well‐known...
Asynchronous Rumor Spreading on Random Graphs
2017,
We perform a thorough study of various characteristics of the asynchronous push–pull protocol for...
Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT
2017,
We present several sparsification lower and upper bounds for classic problems in graph theory and logic....
Connectivity Graphs of Uncertainty Regions
2017,
We study connectivity relations among points, where the precise location of each input point lies in a...
Improved Algorithms for Distributed Entropy Monitoring
2017,
Modern data management systems often need to deal with massive, dynamic and inherently distributed data...
Stable Matching with Network Externalities
2017,
We study the stable roommates problem in networks where players are embedded in a social context and may...
On the Approximability of Digraph Ordering
2017,
Given an n ‐vertex digraph D = ( V , A ) the Max ‐ k ‐ Ordering problem is to compute...
Strong ETH and Resolution via Games and the Multiplicity of Strategies
2017,
We consider a proof system intermediate between regular Resolution, in which no variable can be resolved...
Parameterized Complexity of Sparse Linear Complementarity Problems
2017,
In this paper, we study the parameterized complexity of the linear complementarity problem (LCP), which is...
Papers per page:

Paper Filter