Outputs (2)

Disjunctive Temporal Problems under Structural Restrictions (2021)
Presentation / Conference Contribution
Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021, February). Disjunctive Temporal Problems under Structural Restrictions. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada

The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.’s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability... Read More about Disjunctive Temporal Problems under Structural Restrictions.

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration (2021)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109. https://doi.org/10.1002/jgt.22683

We continue research into a well-studied family of problems that ask whether the vertices of a given graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We consider the ca... Read More about Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration.