License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.47
URN: urn:nbn:de:0030-drops-115430
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11543/
Go to the corresponding LIPIcs Volume Portal

Bar-Noy, Amotz ; Choudhary, Keerti ; Peleg, David ; Rawitz, Dror

Efficiently Realizing Interval Sequences

pdf-format:
LIPIcs-ISAAC-2019-47.pdf (0.6 MB)

Abstract

We consider the problem of realizable interval-sequences. An interval sequence comprises of n integer intervals [a_i,b_i] such that 0 <= a_i <= b_i <= n-1, and is said to be graphic/realizable if there exists a graph with degree sequence, say, D=(d_1,...,d_n) satisfying the condition a_i <= d_i <= b_i, for each i in [1,n]. There is a characterisation (also implying an O(n) verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdös-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in o(n^2) time.
In this paper, we provide an O(n log n) time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length p non-graphic sequence to a graphic one.

BibTeX - Entry

@InProceedings{barnoy_et_al:LIPIcs:2019:11543,
  author =	{Amotz Bar-Noy and Keerti Choudhary and David Peleg and Dror Rawitz},
  title =	{{Efficiently Realizing Interval Sequences}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11543},
  URN =		{urn:nbn:de:0030-drops-115430},
  doi =		{10.4230/LIPIcs.ISAAC.2019.47},
  annote =	{Keywords: Graph realization, graphic sequence, interval sequence}
}

Keywords: Graph realization, graphic sequence, interval sequence
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI