Search Results

Documents authored by Bonsma, Paul

Document
DOI: 10.4230/LIPIcs.MFCS.2016.20
Using Contracted Solution Graphs for Solving Reconfiguration Problems

Authors: Paul Bonsma and Daniël Paulusma

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without losing any critical information needed to solve the reconfiguration problem under consideration. As an example, we consider a well-studied problem: given two k-colorings alpha and beta of a graph G, can alpha be modified into beta by recoloring one vertex of G at a time, while maintaining a k-coloring throughout? By applying our method in combination with a thorough exploitation of the graph structure we obtain a polynomial-time algorithm for (k-2)-connected chordal graphs.
Cite as

Paul Bonsma and Daniël Paulusma. Using Contracted Solution Graphs for Solving Reconfiguration Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bonsma_et_al:LIPIcs.MFCS.2016.20,
  author =	{Bonsma, Paul and Paulusma, Dani\"{e}l},
  title =	{{Using Contracted Solution Graphs for Solving Reconfiguration Problems}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.20},
  URN =		{urn:nbn:de:0030-drops-64351},
  doi =		{10.4230/LIPIcs.MFCS.2016.20},
  annote =	{Keywords: reconfiguration, contraction, dynamic programming, graph coloring}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.337
Rerouting shortest paths in planar graphs

Authors: Paul Bonsma

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.
Cite as

Paul Bonsma. Rerouting shortest paths in planar graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 337-349, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bonsma:LIPIcs.FSTTCS.2012.337,
  author =	{Bonsma, Paul},
  title =	{{Rerouting shortest paths in planar graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{337--349},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.337},
  URN =		{urn:nbn:de:0030-drops-38715},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.337},
  annote =	{Keywords: shortest path, rerouting, reconfiguration problem, planar graph, polynomial time, dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.531
Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces

Authors: Paul Bonsma

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
The Subgraph Isomorphism problem asks, given a host graph G on n vertices and a pattern graph P on k vertices, whether G contains a subgraph isomorphic to P. The restriction of this problem to planar graphs has often been considered. After a sequence of improvements, the current best algorithm for planar graphs is a linear time algorithm by Dorn (STACS '10), with complexity 2^{O(k)} O(n). We generalize this result, by giving an algorithm of the same complexity for graphs that can be embedded in surfaces of bounded genus. In addition, we simplify the algorithm and analysis. The key to these improvements is the introduction of surface split decompositions for bounded genus graphs, which generalize sphere cut decompositions for planar graphs. We extend the algorithm for the problem of counting and generating all subgraphs isomorphic to P, even for the case where P is disconnected. This answers an open question by Eppstein (JGAA '99).
Cite as

Paul Bonsma. Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 531-542, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bonsma:LIPIcs.STACS.2012.531,
  author =	{Bonsma, Paul},
  title =	{{Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{531--542},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.531},
  URN =		{urn:nbn:de:0030-drops-34224},
  doi =		{10.4230/LIPIcs.STACS.2012.531},
  annote =	{Keywords: Analysis of algorithms, parameterized algorithms, graphs on surfaces, subgraph isomorphism, dynamic programming, branch decompositions, counting probl}
}
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 About DROPS Imprint Privacy Contact