Linearity is strictly more powerful than contiguity for encoding graphs

DOI10.1016/j.disc.2016.03.006zbMath1337.05106OpenAlexW1142119968MaRDI QIDQ284761

Christophe Crespelle, Kévin Perrot, Tien-Nam Le, Thi Ha Duong Phan

Publication date: 18 May 2016

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

Full work available at URL: https://doi.org/10.1016/j.disc.2016.03.006

zbMATH Keywords

contiguitycographslinearitygraph encoding

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Uses Software

• WebGraph

Cites Work

• (Nearly-)tight bounds on the contiguity and linearity of cographs
• On the succinct representation of graphs
• Complement reducible graphs
• Graph compression by BFS
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Graph minor theory
• Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs
• Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search
• The Compactness of Interval Routing
• Linear-Time Constant-Ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs
• Permuting Web and Social Graphs
• Codes for the World Wide Web

This page was built for publication: Linearity is strictly more powerful than contiguity for encoding graphs