DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.27

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.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}
}

Search Results

Documents authored by Yehezkel, Elad

Selected Neighbor Degree Forest Realization

Abstract

Cite as

Thanks for your feedback!

Could not send message