Reconstructing a Graph from its Neighborhood Lists

DOI10.1017/S0963548300000535MaRDI QIDQ4290082zbMATH OpenOpenAlexFDO

Authors Martin Aigner, Eberhard Triesch

Publication date 12 July 1994

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300000535

zbMATH Keywords

bipartite graphsdecision problemisomorphismNP-completereconstructing

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 970793
• scientific article; zbMATH DE number 4103126
• Neighborhood reconstruction and cancellation of graphs
• Realizability and uniqueness in graphs
• Building graphs from colored trees

Cites work

• Some NP-Complete Problems Similar to Graph Isomorphism

Cited in

(11)

• Realizability and uniqueness in graphs
• Graph exponentiation and neighborhood reconstruction
• Neighborhood degree lists of graphs
• Reconstructing cactus graphs from shortest path information (extended abstract)
• On the complexity of reconstructing H-free graphs from their Star Systems
• Reconstructing trees from digitally convex sets
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• scientific article; zbMATH DE number 1047709 (Why is no real title available?)
• scientific article; zbMATH DE number 1094128 (Why is no real title available?)
• On the Complexity of Reconstructing H-free Graphs from Their Star Systems
• Neighborhood hypergraphs of digraphs and some matrix permutation problems

This page was built for publication: Reconstructing a Graph from its Neighborhood Lists

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