Relaxed and approximate graph realizations
From MaRDI portal
Publication:2115836
DOI10.1007/978-3-030-79987-8_1OpenAlexW3177066272MaRDI QIDQ2115836
David Peleg, Toni Böhnlein, Mor Perry, Amotz Bar-Noy, Dror Rawitz
Publication date: 22 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-79987-8_1
Related Items (3)
Degree realization by bipartite multigraphs ⋮ Composed degree-distance realizations of graphs ⋮ Composed degree-distance realizations of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constructive extensions of two results on graphic sequences
- A simple existence criterion for \((g<f)\)-factors
- Conditions for sequences to be r-graphic
- A congruence theorem for trees
- A theorem on flows in networks
- Zero-one matrices with zero trace
- A constructive algorithm for realizing a distance matrix
- Binary matrices under the microscope: A tomographical problem
- An algorithm and its role in the study of optimal graph realizations of distance matrices
- Scanning integer matrices by means of two rectangular windows
- Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
- A short constructive proof of the Erdős-Gallai characterization of graphic lists
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
- A simple criterion on degree sequences of graphs
- Linear-time certifying algorithms for near-graphical sequences
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- On optimal realizations of finite metric spaces by graphs
- A fast algorithm for constructing trees from distance matrices
- The splittance of a graph
- Graph factors
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- Contributions to the theory of graphic sequences
- On the realization of a (p,s)-digraph with prescribed degrees
- Realizability and uniqueness in graphs
- Decomposition of graphical sequences and unigraphs
- Solution to a problem on degree sequences of graphs
- Discrete tomography. Foundations, algorithms, and applications
- Distance realization problems with applications to internet tomography
- Homogeneous subsets of \(\mathbb Z^2\) and plane tilings
- Planar bipartite biregular degree sequences
- Game theoretical modelling of a dynamically evolving network. I: General target sequences
- A dynamic network population model with strategic link formation governed by individual preferences
- On forcibly hereditary P-graphical sequences
- A note on a theorem of Erdős and Gallai
- Service chain placement in SDNs
- Graphic deviation
- Algorithms for constructing graphs and digraphs with given valences and factors
- A remark concerning graphical sequences
- An Approximation Algorithm for Path Computation and Function Placement in SDNs
- A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
- Sufficient Conditions for Graphicality of Bidegree Sequences
- Uniqueness in Discrete Tomography: Three Remarks and a Corollary
- A remark on the existence of finite graphs
- Combinatorial Properties of Matrices of Zeros and Ones
- Graphs and degree sequences. II
- Graphic sequences of trees and a problem of Frobenius
- Degree-based graph construction
- Graphs and degree sequences: Canonical decomposition
- A simple proof of the Erdos-Gallai theorem on graph sequences
- Graphs and degree sequences. I
- An Optimality Criterion for Graph Embeddings of Metrics
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Properties of a Class of (0,1)-Matrices Covering a given Matrix
- Threshold Sequences
- Seven criteria for integer sequences being graphic
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Graphs and degree sequences: A survey. III
- The distance matrix of a graph and its tree realization
- On Planar Graphical Degree Sequences
- Recognition of Tree Metrics
- Fast Parallel Recognition of Ultrametrics and Tree Metrics
- On Double-Resolution Imaging and Discrete Tomography
- Reconstructing Binary Matrices under Window Constraints from their Row and Column Sums
- Dynamic discrete tomography
- Efficiently Realizing Interval Sequences
- An algorithmic proof of Tutte's f-factor theorem
- Distance matrix of a graph and its realizability
- On Determining Minimal Singularities for the Realizations of an Incidence Sequence
- Ulam's Conjecture and Graph Reconstructions
- Minimal Number of Multiple Edges in Realization of an Incidence Sequence Without Loops
- Subgraphs with prescribed valencies
- On Determining the Minimum Number of Multiple Edges for an Incidence Sequence
- Fast Sequential Creation of Random Realizations of Degree Sequences
- The Generalized Microscopic Image Reconstruction Problem
- NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
- Composed degree-distance realizations of graphs
- On-line path computation and function placement in SDNs
This page was built for publication: Relaxed and approximate graph realizations
