Efficiently Realizing Interval Sequences
From MaRDI portal
Publication:5138976
DOI10.1137/20M1326489zbMath1453.05123arXiv1912.13287MaRDI QIDQ5138976
Keerti Choudhary, Amotz Bar-Noy, 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
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Constructive extensions of two results on graphic sequences
- A simple existence criterion for \((g<f)\)-factors
- Zero-one matrices with zero trace
- A short constructive proof of the Erdős-Gallai characterization of graphic lists
- Linear-time certifying algorithms for near-graphical sequences
- Graph factors
- On the realization of a (p,s)-digraph with prescribed degrees
- Eccentric sequences in graphs
- Eccentric sequences and eccentric sets in graphs
- Realizability and uniqueness in graphs
- Solution to a problem on degree sequences of graphs
- Realizability of graph specifications: characterizations and algorithms
- Realization of set functions as cut functions of graphs and hypergraphs
- A note on a theorem of Erdős and Gallai
- Threshold graphs and related topics
- Graph profile realizations and applications to social networks
- Algorithms for constructing graphs and digraphs with given valences and factors
- A remark on the existence of finite graphs
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Multi-Terminal Network Flows
- Properties of a Class of (0,1)-Matrices Covering a given Matrix
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- An algorithmic proof of Tutte's f-factor theorem
- Subgraphs with prescribed valencies
- On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
- NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
This page was built for publication: Efficiently Realizing Interval Sequences
