Succinct representation of general unlabeled graphs

DOI10.1016/0166-218X(90)90011-ZMaRDI QIDQ2277480zbMATH OpenFDO

Authors Moni Naor

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(90)90011-Z

zbMATH Keywords

binary encoding

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Review text

What is the shortest possible binary encoding of a simple graph on n vertices if the ordering of the vertices is irrelevant (unlabeled)? In this paper a technique is indicated in order to achieve the theoretical lower bound of \(\left( \begin{matrix} n\\ 2\end{matrix} \right)-n \log_ 2n+O(n)\) in linear time.

Recommendations

• On the succinct representation of graphs
• Succinct Representations of Arbitrary Graphs
• Succinct encoding of arbitrary graphs
• Short encodings of planar graphs and maps
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge

Cites work

• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• On the succinct representation of graphs

Cited in

(14)

• On the OBDD size for graphs of bounded tree- and clique-width
• Simple planar graph partition into three forests
• Short encodings of planar graphs and maps
• Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
• Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
• A compact encoding of unordered binary trees
• Succinct Representations of Arbitrary Graphs
• scientific article; zbMATH DE number 4035881 (Why is no real title available?)
• scientific article; zbMATH DE number 1029246 (Why is no real title available?)
• scientific article; zbMATH DE number 2032369 (Why is no real title available?)
• On Non-Eliminative Structuralism. Unlabeled Graphs as a Case Study, Part B†
• Finite presentation of homogeneous graphs, posets and Ramsey classes
• Graph compression and the zeros of polynomials
• Quick encoding of plane graphs in \(\log _{2}14\) bits per edge

This page was built for publication: Succinct representation of general unlabeled graphs

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