Space-efficient vertex separators for treewidth
From MaRDI portal
Publication:2165026
DOI10.1007/s00453-022-00967-3OpenAlexW2954852478MaRDI QIDQ2165026
Andrej Sajenko, Frank Kammer, Johannes Meintrup
Publication date: 18 August 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.00676
Related Items (1)
Cites Work
- Unnamed Item
- Space-efficient biconnected components and recognition of outerplanar graphs
- Approximation algorithms for treewidth
- Selection and sorting with limited storage
- Space-efficient Euler partition and bipartite edge coloring
- Graph minors. XIII: The disjoint paths problem
- In-place initializable arrays
- Rank-select indices without tears
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Space efficient linear time algorithms for BFS, DFS and applications
- Quantitative analysis of smart contracts
- Succinct representation of labeled graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- Streaming Kernelization
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
- Improved approximation algorithms for minimum-weight vertex separators
- Graph minors. II. Algorithmic aspects of tree-width
- Membership in Constant Time and Almost-Minimum Space
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
- Simple 2^f-Color Choice Dictionaries
- On-the-Fly Array Initialization in Less Space
- Parameterized Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Space-efficient vertex separators for treewidth
