I/O-efficient algorithms for graphs of bounded treewidth

DOI 10.1007/s00453-007-9131-5</link>zbMath 1213.05249</link>OpenAlex W3139402347</link>MaRDI QID Q834592</link>

Anil Maheshwari, Norbert Zeh

Publication date: 27 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9131-5

zbMATH Keywords

algorithmsgraph algorithmsexternal memory algorithmsbounded treewidth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Algorithms for parallel memory, I: Two-level memories
• Algorithms for parallel memory. II: Hierarchical multilevel memories
• Treewidth. Computations and approximations
• A functional approach to external graph algorithms
• Efficient external memory algorithms by simulating coarse-grained parallel algorithms
• The buffer tree: A technique for designing batched external data structures
• On external-memory MST, SSSP and multi-way planar graph separation
• Algorithms finding tree-decompositions of graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Easy problems for tree-decomposable graphs
• Three Partition Refinement Algorithms
• Algorithmic Aspects of Vertex Elimination on Graphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• An algebraic theory of graph reduction
• On External-Memory Planar Depth First Search
• I/O-Optimal Algorithms for Outerplanar Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Efficient Parallel Algorithms for Chordal Graphs
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Theorem on Boolean Matrices
• Algorithms - ESA 2003
• Parallel algorithms for series parallel graphs and graphs with treewidth two

This page was built for publication: I/O-efficient algorithms for graphs of bounded treewidth