Reconstructing graphs from cut-set sizes
type: Item
instance of: scholarly article
title: Reconstructing graphs from cut-set sizes
zbMATH Open document ID: 0695.05054
DOI: 10.1016/0020-0190(89)90012-4
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: The n vertices of a graph embedded in the plane are in general position and the edges are straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. It is shown that such graphs are completely reconstructible from \(\left( \begin{matrix} n\\ 2\end{matrix} \right)\) cut-set probes and that this number of probes is necessary. For generalised cut-set probes, which determine the size of any cut-set of the graph, \(O(n^ 2/\log n)\) are shown to be necessary and sufficient for reconstruction.
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 4137816
zbMATH Keywords: cut-set probe
zbMATH Keywords: completely reconstructible
author: Steven Skiena
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90012-4
OpenAlex ID: W2051329734
cites work: A generalized model for understanding evasiveness
cites work: Q5422499
cites work: Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
cites work: Q5682013
Recommended article: Size reconstructibility of graphs
Recommended article: On Reconstructing Graphs and Their Complements
Recommended article: On reconstruction of graphs
Recommended article: Q3480086
Recommended article: Parameterizing cut sets in a graph by the number of their components
Recommended article: Parameterizing Cut Sets in a Graph by the Number of Their Components
Recommended article: Q3029040
Recommended article: A reduction of the graph reconstruction conjecture
Recommended article: Reconstructing graphs from size and degree properties of their induced \(k\)-subgraphs
Recommended article: On the complexity of graph reconstruction
description: scientific article; zbMATH DE number 4137816