2 Search Results for "Richmond, Tom"


Document
Minimum Separator Reconfiguration

Authors: Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.

Cite as

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
  author =	{C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
  title =	{{Minimum Separator Reconfiguration}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9},
  URN =		{urn:nbn:de:0030-drops-194288},
  doi =		{10.4230/LIPIcs.IPEC.2023.9},
  annote =	{Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
Continued Radicals

Authors: Jamie Johnson and Tom Richmond

Published in: Dagstuhl Seminar Proceedings, Volume 4351, Spatial Representation: Discrete vs. Continuous Computational Models (2005)


Abstract
A nested radical with terms $a_1, a_2, \ldots , a_N$ is an expression of form $\sqrt{a_N + \cdots + \sqrt{a_2 + \sqrt{a_1}}}$. The limit as $N$ approaches infinity of such an expression, if it exists, is called a continued radical. We consider the set of real numbers $S(M)$ representable as a continued radical whose terms $a_1, a_2, \ldots$ are all from a finite set $M$ of nonnegative real numbers. We give conditions on the set $M$ for $S(M)$ to be (a) an interval, and (b) homeomorphic to the Cantor set.

Cite as

Jamie Johnson and Tom Richmond. Continued Radicals. In Spatial Representation: Discrete vs. Continuous Computational Models. Dagstuhl Seminar Proceedings, Volume 4351, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{johnson_et_al:DagSemProc.04351.10,
  author =	{Johnson, Jamie and Richmond, Tom},
  title =	{{Continued Radicals}},
  booktitle =	{Spatial Representation: Discrete vs. Continuous Computational Models},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4351},
  editor =	{Ralph Kopperman and Michael B. Smyth and Dieter Spreen and Julian Webster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04351.10},
  URN =		{urn:nbn:de:0030-drops-1286},
  doi =		{10.4230/DagSemProc.04351.10},
  annote =	{Keywords: Continued radical}
}
  • Refine by Author
  • 1 C. M. Gomes, Guilherme
  • 1 C. van der Zanden, Tom
  • 1 F. dos Santos, Vinicius
  • 1 Johnson, Jamie
  • 1 Legrand-Duchesne, Clément
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Continued radical
  • 1 combinatorial reconfiguration
  • 1 kernelization
  • 1 minimum separators
  • 1 parameterized complexity

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2005
  • 1 2023

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