1 Search Results for "Subramanya, Vijay"

Document
DOI: 10.4230/LIPIcs.MFCS.2018.75
Reconfiguration of Graph Minors

Authors: Benjamin Moore, Naomi Nishimura, and Vijay Subramanya

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H. We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.
Cite as

Benjamin Moore, Naomi Nishimura, and Vijay Subramanya. Reconfiguration of Graph Minors. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{moore_et_al:LIPIcs.MFCS.2018.75,
  author =	{Moore, Benjamin and Nishimura, Naomi and Subramanya, Vijay},
  title =	{{Reconfiguration of Graph Minors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.75},
  URN =		{urn:nbn:de:0030-drops-96573},
  doi =		{10.4230/LIPIcs.MFCS.2018.75},
  annote =	{Keywords: reconfiguration, graph minors, graph algorithms}
}
  • Refine by Author
  • 1 Moore, Benjamin
  • 1 Nishimura, Naomi
  • 1 Subramanya, Vijay

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory

  • Refine by Keyword
  • 1 graph algorithms
  • 1 graph minors
  • 1 reconfiguration

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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