(Nearly-)tight bounds on the contiguity and linearity of cographs

DOI10.1016/j.tcs.2013.11.036zbMath1279.68103OpenAlexW2000789139WikidataQ58172954 ScholiaQ58172954MaRDI QIDQ393888

Christophe Crespelle, Philippe Gambette

Publication date: 24 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.036

zbMATH Keywords

contiguitycographslinearitygraph encoding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

The Micro-world of Cographs ⋮ Linearity is strictly more powerful than contiguity for encoding graphs ⋮ The micro-world of cographs ⋮ Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• On the succinct representation of graphs
• Learning decision trees from random examples
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Graph minor theory
• Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search
• Graph Classes: A Survey
• The Compactness of Interval Routing
• Codes for the World Wide Web

This page was built for publication: (Nearly-)tight bounds on the contiguity and linearity of cographs