16 citations · 17 across the 3 of their papers we have counts for
3 papers
cs.CC2025
Non-crossing -graphs: a generalization of proper interval graphs admitting FPT algorithms
Flavia Bonomo-Braberman, Nick Brettell, Noleen Köhler +2
We prove new parameterized complexity results for the FO Model Checking problem on a well-known generalization of interval and circular-arc graphs: the class of -graphs, for any…
cs.DM2018★ 1 cited
Graph Isomorphism for -free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski +3
We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs and for all but six pairs $(H_1,H_2)…
cs.CC2011★ 16 cited
The Computational Complexity of Disconnected Cut and 2K2-Partition
Barnaby Martin, Daniel Paulusma
For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the probl…