Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs

DOI10.1007/978-3-030-92681-6_33OpenAlexW3195424718MaRDI QIDQ2150567

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

Publication date: 29 June 2022

Full work available at URL: https://arxiv.org/abs/2108.10776

zbMATH Keywords

series-parallel graphscactus graphssuccinct encodingspace efficient data structures

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Succinct data structure for path graphs ⋮ Succinct representation for (non)deterministic finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Succinct encoding of arbitrary graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Structure and linear time recognition of 3-leaf powers
• Succinct data structures for families of interval graphs
• On the succinct representation of equivalence classes
• A uniform paradigm to succinctly encode various families of trees
• Enumeration and limit laws for series-parallel graphs
• Compressed suffix trees with full functionality
• Succinct Representation of Balanced Parentheses and Static Trees
• Fully Functional Static and Dynamic Succinct Trees
• BOUNDING THE NUMBER OF REDUCED TREES, COGRAPHS, AND SERIES-PARALLEL GRAPHS BY COMPRESSION
• Succinct Representations of Ordinal Trees
• Succinct Representations of Separable Graphs
• Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems
• The Recognition of Series Parallel Digraphs
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• An Exact Enumeration of Distance-Hereditary Graphs
• Enumeration of labeled block-cactus graphs

This page was built for publication: Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs