Reconstructing graphs from cut-set sizes

Steven S. Skiena

doi:10.1016/0020-0190(89)90012-4

Reconstructing graphs from cut-set sizes

Steven S. Skiena

Computer Science

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Consider an embedded graph G whose n vertices are points in general position in the plane and whose edges are all straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. We show that all such graphs are completely reconstructible with (ⁿ₂) cut-set probes and that (ⁿ₂) probes are necessary. For a generalized cut-set probe, which can determine the size of any cut-set of a graph, we prove THgr; (n²/log n) bounds for reconstruction.

Original language	English
Pages (from-to)	123-127
Number of pages	5
Journal	Information Processing Letters
Volume	32
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(89)90012-4
State	Published - Aug 24 1989

Keywords

combinatorial geometry
cut-sets
evasiveness
Graph theory
probing

Access to Document

10.1016/0020-0190(89)90012-4

Cite this

@article{6272a999f73f4a81b33d6b795c1083ee,

title = "Reconstructing graphs from cut-set sizes",

abstract = "Consider an embedded graph G whose n vertices are points in general position in the plane and whose edges are all straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. We show that all such graphs are completely reconstructible with (n2) cut-set probes and that (n2) probes are necessary. For a generalized cut-set probe, which can determine the size of any cut-set of a graph, we prove THgr; (n2/log n) bounds for reconstruction.",

keywords = "combinatorial geometry, cut-sets, evasiveness, Graph theory, probing",

author = "Skiena, \{Steven S.\}",

year = "1989",

month = aug,

day = "24",

doi = "10.1016/0020-0190(89)90012-4",

language = "English",

volume = "32",

pages = "123--127",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "3",

}

TY - JOUR

T1 - Reconstructing graphs from cut-set sizes

AU - Skiena, Steven S.

PY - 1989/8/24

Y1 - 1989/8/24

N2 - Consider an embedded graph G whose n vertices are points in general position in the plane and whose edges are all straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. We show that all such graphs are completely reconstructible with (n2) cut-set probes and that (n2) probes are necessary. For a generalized cut-set probe, which can determine the size of any cut-set of a graph, we prove THgr; (n2/log n) bounds for reconstruction.

AB - Consider an embedded graph G whose n vertices are points in general position in the plane and whose edges are all straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. We show that all such graphs are completely reconstructible with (n2) cut-set probes and that (n2) probes are necessary. For a generalized cut-set probe, which can determine the size of any cut-set of a graph, we prove THgr; (n2/log n) bounds for reconstruction.

KW - combinatorial geometry

KW - cut-sets

KW - evasiveness

KW - Graph theory

KW - probing

UR - https://www.scopus.com/pages/publications/0024719516

U2 - 10.1016/0020-0190(89)90012-4

DO - 10.1016/0020-0190(89)90012-4

M3 - Article

AN - SCOPUS:0024719516

SN - 0020-0190

VL - 32

SP - 123

EP - 127

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

Reconstructing graphs from cut-set sizes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this