Linearity is strictly more powerful than contiguity for encoding graphs

DOI10.1016/J.DISC.2016.03.006MaRDI QIDQ284761zbMATH OpenOpenAlexFDO

Authors Christophe Crespelle, Tien-Nam Le, Kévin Perrot, 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

cographscontiguitygraph encodinglinearity

Mathematics Subject Classification ID

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

Recommendations

• Linearity is strictly more powerful than contiguity for encoding graphs
• (Nearly-)tight bounds on the contiguity and linearity of cographs
• Linear-time constant-ratio approximation algorithm and tight bounds for the contiguity of cographs
• On the Encoding of Relations by Graphs

Cites work

• (Nearly-)tight bounds on the contiguity and linearity of cographs
• Codes for the World Wide Web
• Complement reducible graphs
• Efficient neighborhood encoding for interval graphs and permutation graphs and O(n) breadth-first search
• Graph compression by BFS
• Graph minor theory
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Linear-time constant-ratio approximation algorithm and tight bounds for the contiguity of cographs
• Linearity is strictly more powerful than contiguity for encoding graphs
• On the succinct representation of graphs
• Permuting web and social graphs
• The Compactness of Interval Routing

Cited in

(2)

• Linearity is strictly more powerful than contiguity for encoding graphs
• Linear-time constant-ratio approximation algorithm and tight bounds for the contiguity of cographs

Describes a project that uses

Uses Software

• WebGraph

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

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