1. Succinct Data Structures for Small Clique-Width Graphs
- Author
-
Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane, and Srinivasa Rao Satti
- Subjects
Degree (graph theory) ,Open problem ,0102 computer and information sciences ,02 engineering and technology ,Data structure ,Binary logarithm ,01 natural sciences ,Combinatorics ,Succinct data structure ,010201 computation theory & mathematics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Clique-width ,0202 electrical engineering, electronic engineering, information engineering ,Adjacency list ,020201 artificial intelligence & image processing ,Constant (mathematics) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability. In this paper we design a succinct data structure for graphs on $n$ vertices whose clique-width is at most $k \leq \epsilon \sqrt{\log n / \log \log n}$ for some constant $0 , along with supporting degree, adjacency, neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018). more...
- Published
- 2021
- Full Text
- View/download PDF