All Outputs (10)

Finding cactus roots in polynomial time (2017)
Journal Article
Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admi... Read More about Finding cactus roots in polynomial time.

Independent feedback vertex sets for graphs of bounded diameter (2017)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback... Read More about Independent feedback vertex sets for graphs of bounded diameter.

Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity (2017)
Journal Article
Chiarelli, N., Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2018). Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoretical Computer Science, 705, 75-83. https://doi.org/10.1016/j.tcs.2017.09.033

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like their original counterparts, these variants are NP-c... Read More about Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.

Contracting Bipartite Graphs to Paths and Cycles (2017)
Journal Article
Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013

Testing if a given graph G contains the k -vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. However, the situation changes for the problem of checking if a graph can be modified into Pk by using only edge contr... Read More about Contracting Bipartite Graphs to Paths and Cycles.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2017)
Journal Article
Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely ma... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Colouring Diamond-free Graphs (2017)
Journal Article
Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof i... Read More about Colouring Diamond-free Graphs.

A linear kernel for finding square roots of almost planar graphs (2017)
Journal Article
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are at distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root.... Read More about A linear kernel for finding square roots of almost planar graphs.

Computing square roots of graphs with low maximum degree (2017)
Journal Article
Cochefert, M., Couturier, J., Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics, 248, 93-101. https://doi.org/10.1016/j.dam.2017.04.041

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known... Read More about Computing square roots of graphs with low maximum degree.

Bounding the Clique-Width of H-free Chordal Graphs (2017)
Journal Article
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory, 86(1), 42-77. https://doi.org/10.1002/jgt.22111

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le, and Mosca erroneously claime... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

The Stable Fixtures Problem with Payments (2017)
Journal Article
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior, 108, 245-268. https://doi.org/10.1016/j.geb.2017.02.002

We consider multiple partners matching games (G,b,w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite, these games are called multiple partners assignment games. We give a polynomial-time algor... Read More about The Stable Fixtures Problem with Payments.