4 Search Results for "N. Zehmakan, Ahad"

Document
DOI: 10.4230/LIPIcs.GD.2025.5
Constrained Flips in Plane Spanning Trees

Authors: Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A flip in a plane spanning tree T is the operation of removing one edge from T and adding another edge such that the resulting structure is again a plane spanning tree. For trees on a set of points in convex position we study two classic types of constrained flips: (1) Compatible flips are flips in which the removed and inserted edge do not cross each other. We relevantly improve the previous upper bound of 2n-O(√n) on the diameter of the compatible flip graph to (5n/3)-O(1), by this matching the upper bound for unrestricted flips by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber [SODA 2025] up to an additive constant of 1. We further show that no shortest compatible flip sequence removes an edge that is already in its target position. Using this so-called happy edge property, we derive a fixed-parameter tractable algorithm to compute the shortest compatible flip sequence between two given trees. (2) Rotations are flips in which the removed and inserted edge share a common vertex. Besides showing that the happy edge property does not hold for rotations, we improve the previous upper bound of 2n-O(1) for the diameter of the rotation graph to (7n/4)-O(1).
Cite as

Oswin Aichholzer, Joseph Dorfer, and Birgit Vogtenhuber. Constrained Flips in Plane Spanning Trees. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.5,
  author =	{Aichholzer, Oswin and Dorfer, Joseph and Vogtenhuber, Birgit},
  title =	{{Constrained Flips in Plane Spanning Trees}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.5},
  URN =		{urn:nbn:de:0030-drops-249913},
  doi =		{10.4230/LIPIcs.GD.2025.5},
  annote =	{Keywords: Non-crossing spanning trees, Flip Graphs, Diameter, Complexity, Happy edges}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.47
Reconfigurations of Plane Caterpillars and Paths (Poster Abstract)

Authors: Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Let S be a point set in the plane, and let 𝒫(S) and 𝒞(S) be the sets of all plane spanning paths and caterpillars on S. We study reconfiguration operations on 𝒫(S) and 𝒞(S). In particular, we prove that all of the commonly studied reconfigurations on plane spanning trees still yield connected reconfiguration graphs for caterpillars when S is in convex position. If S is in general position, we show that the rotation, compatible flip and flip graphs of 𝒞(S) are connected while the slide graph is sometimes disconnected, but always has a component of size 1/4(3ⁿ-1). We then study sizes of connected components in reconfiguration graphs of plane spanning paths. In this direction, we show that no component of size at most 7 can exist in the flip graph on 𝒫(S).
Cite as

Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić. Reconfigurations of Plane Caterpillars and Paths (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 47:1-47:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.47,
  author =	{Anti\'{c}, Todor and Gamboa Quintero, Guillermo and Gli\v{s}i\'{c}, Jelena},
  title =	{{Reconfigurations of Plane Caterpillars and Paths}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{47:1--47:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.47},
  URN =		{urn:nbn:de:0030-drops-250337},
  doi =		{10.4230/LIPIcs.GD.2025.47},
  annote =	{Keywords: reconfiguration graph, caterpillar, path, geometric graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.5
Two Phase Transitions in Two-Way Bootstrap Percolation

Authors: Ahad N. Zehmakan

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Consider a graph G and an initial random configuration, where each node is black with probability p and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least r black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a d-dimensional torus and identify the threshold values.
Cite as

Ahad N. Zehmakan. Two Phase Transitions in Two-Way Bootstrap Percolation. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{zehmakan:LIPIcs.ISAAC.2019.5,
  author =	{Zehmakan, Ahad N.},
  title =	{{Two Phase Transitions in Two-Way Bootstrap Percolation}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.5},
  URN =		{urn:nbn:de:0030-drops-115017},
  doi =		{10.4230/LIPIcs.ISAAC.2019.5},
  annote =	{Keywords: bootstrap percolation, cellular automata, phase transition, d-dimensional torus, r-threshold model, biased majority}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.4
Opinion Forming in Erdös-Rényi Random Graph and Expanders

Authors: Ahad N. Zehmakan

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Assume for a graph G=(V,E) and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the Erdös-Rényi random graph G_{n,p} and regular expanders. First we consider the behavior of the majority model on G_{n,p} with an initial random configuration, where each node is blue independently with probability p_b and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely (log n)/n. Furthermore, we say a graph G is lambda-expander if the second-largest absolute eigenvalue of its adjacency matrix is lambda. We prove that for a Delta-regular lambda-expander graph if lambda/Delta is sufficiently small, then the majority model by starting from (1/2-delta)n blue nodes (for an arbitrarily small constant delta>0) results in fully red configuration in sub-logarithmically many rounds. Roughly speaking, this means the majority model is an "efficient" and "fast" density classifier on regular expanders. As a by-product of our results, we show regular Ramanujan graphs are asymptotically optimally immune, that is for an n-node Delta-regular Ramanujan graph if the initial number of blue nodes is s <= beta n, the number of blue nodes in the next round is at most cs/Delta for some constants c,beta>0. This settles an open problem by Peleg [Peleg, 2014].
Cite as

Ahad N. Zehmakan. Opinion Forming in Erdös-Rényi Random Graph and Expanders. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{n.zehmakan:LIPIcs.ISAAC.2018.4,
  author =	{N. Zehmakan, Ahad},
  title =	{{Opinion Forming in Erd\"{o}s-R\'{e}nyi Random Graph and Expanders}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.4},
  URN =		{urn:nbn:de:0030-drops-99529},
  doi =		{10.4230/LIPIcs.ISAAC.2018.4},
  annote =	{Keywords: majority model, random graph, expander graphs, dynamic monopoly, bootstrap percolation}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2019
  • 1 2018

  • Refine by Author
  • 1 Aichholzer, Oswin
  • 1 Antić, Todor
  • 1 Dorfer, Joseph
  • 1 Gamboa Quintero, Guillermo
  • 1 Glišić, Jelena
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorics
  • 2 Theory of computation
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 2 bootstrap percolation
  • 1 Complexity
  • 1 Diameter
  • 1 Flip Graphs
  • 1 Happy edges
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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