Blar i Bergen Open Research Archive på forfatter "Lochet, William"

The directed 2linkage problem with length constraints
BangJensen, J.; Bellitto, Thomas; Lochet, William; Yeo, A. (Journal article; Peer reviewed, 2020) 
Exact and approximate digraph bandwidth
Jain, Pallavi; Kanesh, Lawqueen; Lochet, William; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2019)In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the viewpoint of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ... 
Fault tolerant subgraphs with applications in kernelization
Lochet, William; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav (Journal article; Peer reviewed, 2020)In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ... 
Parameterized Complexity of Directed Spanner Problems
Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)We initiate the parameterized complexity study of minimum tspanner problems on directed graphs. For a positive integer t, a multiplicative tspanner of a (directed) graph G is a spanning subgraph H such that the distance ... 
A Polynomial Kernel for Line Graph Deletion
Lochet, William; Eiben, Eduard (Journal article; Peer reviewed, 2020)The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some ... 
A Polynomial Kernel for PawFree Editing
Eiben, Eduard; Lochet, William; Saurabh, Saket (Journal article; Peer reviewed, 2020)For a fixed graph H, the Hfree Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is ... 
Subdivisions in digraphs of large outdegree or large dichromatic number
Aboulker, Pierre; Cohen, Nathann; Havet, Frederic; Lochet, William; Moura, Phablo F S; Thomasse, Stephan (Journal article; Peer reviewed, 2019)In 1985, Mader conjectured the existence of a function f such that every digraph with minimum outdegree at least f ( k ) contains a subdivision of the transitive tournament of order k . This conjecture is still completely ...