2 Search Results for "Str�mme, Torstein J. F."

Document
DOI: 10.4230/LIPIcs.IPEC.2018.6
Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

Authors: Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
We generalize the family of (sigma, rho)-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-r dominating set and distance-r independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as k-trapezoid graphs, Dilworth k-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, k-polygon graphs, circular arc graphs, complements of d-degenerate graphs, and H-graphs if given an H-representation. To supplement these findings, we show that many classes of (distance) (sigma, rho)-problems are W[1]-hard parameterized by mim-width + solution size.
Cite as

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2018.6,
  author =	{Jaffke, Lars and Kwon, O-joung and Str{\o}mme, Torstein J. F. and Telle, Jan Arne},
  title =	{{Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.6},
  URN =		{urn:nbn:de:0030-drops-102074},
  doi =		{10.4230/LIPIcs.IPEC.2018.6},
  annote =	{Keywords: Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.21
Partial Complementation of Graphs

Authors: Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
A partial complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there a partial complement of G which is in G? We show that this problem can be solved in polynomial time for various choices of the graphs class G, such as bipartite, degenerate, or cographs. We complement these results by proving that the problem is NP-complete when G is the class of r-regular graphs.
Cite as

Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos. Partial Complementation of Graphs. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.SWAT.2018.21,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Str{\o}mme, Torstein J. F. and Thilikos, Dimitrios M.},
  title =	{{Partial Complementation of Graphs}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.21},
  URN =		{urn:nbn:de:0030-drops-88476},
  doi =		{10.4230/LIPIcs.SWAT.2018.21},
  annote =	{Keywords: Partial complementation, graph editing, graph classes}
}
  • Refine by Author
  • 2 Strømme, Torstein J. F.
  • 1 Fomin, Fedor V.
  • 1 Golovach, Petr A.
  • 1 Jaffke, Lars
  • 1 Kwon, O-joung
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Distance Domination Problems
  • 1 Graph Classes
  • 1 Graph Width Parameters
  • 1 Parameterized Complexity
  • 1 Partial complementation
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact