Skip to main content

Research Repository

Advanced Search

Outputs (4)

Combinatorics and Algorithms for Augmenting Graphs (2015)
Journal Article
Dabrowski, K. K., Lozin, V. V., de Werra, D., & Zamaraev, V. (2016). Combinatorics and Algorithms for Augmenting Graphs. Graphs and Combinatorics, 32(4), 1339-1352. https://doi.org/10.1007/s00373-015-1660-0

The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) prob... Read More about Combinatorics and Algorithms for Augmenting Graphs.

Editing to Eulerian graphs (2015)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and dir... Read More about Editing to Eulerian graphs.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, https://doi.org/10.1093/comjnl/bxv096

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Classifying the clique-width of H-free bipartite graphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030

Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induce... Read More about Classifying the clique-width of H-free bipartite graphs.