1 Search Results for "Yehezkel, Elad"


Document
Selected Neighbor Degree Forest Realization

Authors: Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

Cite as

Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel. Selected Neighbor Degree Forest Realization. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2021.27,
  author =	{Bar-Noy, Amotz and Peleg, David and Rawitz, Dror and Yehezkel, Elad},
  title =	{{Selected Neighbor Degree Forest Realization}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.27},
  URN =		{urn:nbn:de:0030-drops-154609},
  doi =		{10.4230/LIPIcs.ISAAC.2021.27},
  annote =	{Keywords: network realization, graph algorithms, lower bound}
}
  • Refine by Author
  • 1 Bar-Noy, Amotz
  • 1 Peleg, David
  • 1 Rawitz, Dror
  • 1 Yehezkel, Elad

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

  • Refine by Keyword
  • 1 graph algorithms
  • 1 lower bound
  • 1 network realization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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