Efficiently realizing interval sequences

DOI10.1137/20M1326489MaRDI QIDQ5138976zbMATH OpenFDO

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

Publication date 4 December 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.13287

zbMATH Keywords

graph realizationgraphic sequenceinterval sequence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider the problem of realizable interval-sequences. An interval sequence comprises of $n$ integer intervals $[a_i,b_i]$ such that $0leq{a}_{i}leq{b}_{i}leqn-1$, and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,ldots,d_n)$ satisfying the condition $a_{i}leq{d}_{i}leq{b}_i$, for each $iin[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 Erdos-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(nlogn)$ 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.

Recommendations

• Linear-time certifying algorithms for near-graphical sequences
• Realizing Degree Sequences in Parallel
• On Erdös-Gallai and Havel-Hakimi algorithms
• scientific article; zbMATH DE number 3966135
• scientific article; zbMATH DE number 4187870

Cites work

• A note on a theorem of Erdős and Gallai
• A remark on the existence of finite graphs
• A short constructive proof of the Erdős-Gallai characterization of graphic lists
• A simple existence criterion for \((g<f)\)-factors
• A variant of Niessen's problem on degree sequences of graphs
• Algorithms for constructing graphs and digraphs with given valences and factors
• An algorithmic proof of Tutte's f-factor theorem
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Constructive extensions of two results on graphic sequences
• Eccentric sequences and eccentric sets in graphs
• Eccentric sequences in graphs
• Graph factors
• Graph profile realizations and applications to social networks
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• Linear-time certifying algorithms for near-graphical sequences
• Multi-Terminal Network Flows
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
• On the realization of a (p,s)-digraph with prescribed degrees
• Properties of a Class of (0,1)-Matrices Covering a given Matrix
• Realizability and uniqueness in graphs
• Realizability of graph specifications: characterizations and algorithms
• Realization of set functions as cut functions of graphs and hypergraphs
• Solution to a problem on degree sequences of graphs
• Subgraphs with prescribed valencies
• Threshold graphs and related topics
• Zero-one matrices with zero trace

Cited in

(7)

• Constraint-directed search for all-interval series
• Relaxed and approximate graph realizations
• Graphic deviation
• scientific article; zbMATH DE number 1714654 (Why is no real title available?)
• scientific article; zbMATH DE number 7651149 (Why is no real title available?)
• Temporal graph realization from fastest paths
• Realizing temporal transportation trees

This page was built for publication: Efficiently realizing interval sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138976)