Succinct data structures for bounded clique-width graphs

DOI10.1016/J.DAM.2024.03.016MaRDI QIDQ6497944zbMATH OpenFDO

Authors Sankardeep Chakraborty, Seungbum Jo, Kunihiko Sadakane, Srinivasa Rao Satti

Publication date 6 May 2024

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

Full work available at URL https://doi.org/10.1016/J.DAM.2024.03.016

zbMATH Keywords

succinct data structurescographsdistance hereditary graphsbounded clique-width graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Graph theory (05C99)

Recommendations

• Compact representation of graphs of small clique-width
• Succinct data structures for families of interval graphs
• Query efficient implementation of graphs of bounded clique-width
• Recent developments on graphs of bounded clique-width
• Succinct encodings for families of interval graphs

Cites work

• scientific article; zbMATH DE number 5506222 (Why is no real title available?)
• scientific article; zbMATH DE number 177438 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• scientific article; zbMATH DE number 7561421 (Why is no real title available?)
• scientific article; zbMATH DE number 7740925 (Why is no real title available?)
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• A uniform paradigm to succinctly encode various families of trees
• Algorithms and Data Structures
• An exact enumeration of distance-hereditary graphs
• Approximating clique-width and branch-width
• Bounding the number of reduced trees, cographs, and series-parallel graphs by compression
• Clique-width is NP-complete
• Compact representation of graphs of small clique-width
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Completely separable graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Graph-Theoretic Concepts in Computer Science
• Indexing graph search trees and applications
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the clique-width of some perfect graph classes
• Powers of distance-hereditary graphs
• Recent developments on graphs of bounded clique-width
• Space-Efficient Data Structures for Lattices
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct encoding of arbitrary graphs
• Succinct encodings for families of interval graphs
• Succinct navigational oracles for families of intersection graphs on a circle
• Succinct permutation graphs
• Succinct representation of balanced parentheses and static trees
• Succinct representations for (non)deterministic finite automata
• Succinct representations of planar maps
• Succinct representations of separable graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Upper bounds to the clique width of graphs

Cited in

(2)

• Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
• Succinct data structures for Baxter permutation and related families

This page was built for publication: Succinct data structures for bounded clique-width graphs

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