5 results
Filters
Settings
Now showing1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Parameterized algorithms for generalizations of directed feedback vertex setPublicationtype: Journal ArticleScopus© Citations 1 149 157 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikesWe consider a fundamental integer programming (IP) model for cost–benefit analysis and flood protection through dike building in the Netherlands, due to Zwaneveld and Verweij (2017). Experimental analysis with data for the IJsselmeer shows that the solution of the linear programming relaxation of the IP model is integral. This naturally leads to question whether the polytope associated to the IP is always integral. In this paper we first give a negative answer to this question by proving the non-integrality of the polytope. Secondly, we establish natural conditions that guarantee the linear programming relaxation of the IP model is integral. We show that these conditions are indeed satisfied by the recent data on flood probabilities, damage and investment costs of IJsselmeer. Finally, we show that the IP model can be solved in polynomial time when the number of dike segments, or the number of feasible barrier heights, are bounded.Publicationtype: Journal Article196 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , 121 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Linear-time recognition of map graphs with outerplanar witnessMap graphs generalize planar graphs and were introduced by Chen et al. (STOC 1998, J. ACM, 2002). They showed that the problem of recognizing map graphs is in by proving the existence of a planar witness graph . Shortly after, Thorup (FOCS 1998) published a polynomial-time recognition algorithm for map graphs. However, the run time of this algorithm is estimated to be for -vertex graphs, and a full description of its details remains unpublished. We give a new and purely combinatorial algorithm that decides whether a graph is a map graph having an outerplanar witness . This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space . In contrast to Thorup’s approach, it computes the witness graph in the affirmative case.Publicationtype: Journal Article128 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Polynomial kernels for deletion to classes of acyclic digraphsWe consider the problem to find a set X of vertices (or arcs) with |X|≤k in a given digraph G such that D=G−X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET (or DIRECTED FEEDBACK ARC SET); the existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider the vertex deletion problem with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of the above three restrictions we can obtain a kernel with kO(1) vertices on general digraphs. We also show that the arc deletion problem with the first two restrictions (out-forest and out-tree) can be solved in polynomial time; this contrasts the status of the vertex deletion problem of these restrictions, which is NP-hard even for acyclic digraphs. The arc and vertex deletion problem with the third restriction (pumpkin), however, can be solved in polynomial time for acyclic digraphs, but becomes NP-hard for general digraphs. We believe that the idea of restricting D could yield new insights towards resolving the status of DIRECTED FEEDBACK VERTEX SET.Publicationtype: Journal Article176