4 papers
Time-inconsistent Planning: Simple Motivation Is Hard to Find
Fedor V. Fomin, Torstein J. F. Strømme
With the introduction of the graph-theoretic time-inconsistent planning model due to Kleinberg and Oren, it has been possible to investigate the computational complexity of how a t…
Partial complementation of graphs
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme +1
A partial complement of the graph is a graph obtained from by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for…
Generalized distance domination problems and their complexity on graphs of bounded mim-width
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme +1
We generalize the family of -problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as dista…
Vertex Cover Structural Parameterization Revisited
Fedor V. Fomin, Torstein J. F. Strømme
A pseudoforest is a graph whose connected components have at most one cycle. Let X be a pseudoforest modulator of graph G, i. e. a vertex subset of G such that G-X is a pseudofores…