BarNoy, Amotz ;
Choudhary, Keerti ;
Peleg, David ;
Rawitz, Dror
Efficiently Realizing Interval Sequences
Abstract
We consider the problem of realizable intervalsequences. An interval sequence comprises of n integer intervals [a_i,b_i] such that 0 <= a_i <= b_i <= n1, 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 intervalsequences, which is a generalization of the ErdösGallai characterisation for graphic sequences. However, given any realizable intervalsequence, 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 nonrealizable, 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 nongraphic sequence to a graphic one.
BibTeX  Entry
@InProceedings{barnoy_et_al:LIPIcs:2019:11543,
author = {Amotz BarNoy 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:147:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11543},
URN = {urn:nbn:de:0030drops115430},
doi = {10.4230/LIPIcs.ISAAC.2019.47},
annote = {Keywords: Graph realization, graphic sequence, interval sequence}
}
28.11.2019
Keywords: 

Graph realization, graphic sequence, interval sequence 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 