Succinct data structures for bounded clique-width graphs

DOI10.1016/J.DAM.2024.03.016MaRDI QIDQ6497944FDOQ6497944

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)

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

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)

Cites Work

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

Cited In (1)

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

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)