Dynamic algorithms for graphs of bounded treewidth

DOI10.1007/S004530010021MaRDI QIDQ1578413zbMATH OpenOpenAlexFDO

Authors Torben Hagerup

Publication date 24 April 2001

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004530010021

zbMATH Keywords

treewidthgraph algorithmmonadic second-order logicpath querydynamic algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Logic in computer science (03B70)

Recommendations

• Dynamic algorithms for graphs of bounded treewidth
• On the treewidth of dynamic graphs
• On the treewidth of dynamic graphs
• scientific article; zbMATH DE number 4060712
• A dynamic data structure for MSO properties in graphs with bounded tree-depth

Cited in

(26)

• Dynamic algorithms for graphs of bounded treewidth
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• scientific article; zbMATH DE number 7310159 (Why is no real title available?)
• Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
• I/O-efficient algorithms for graphs of bounded treewidth
• A \(c^k n\) 5-approximation algorithm for treewidth
• Listing all potential maximal cliques of a graph
• Query efficient implementation of graphs of bounded clique-width
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• On the treewidth of dynamic graphs
• On the treewidth of dynamic graphs
• Parallel preprocessing for path queries without concurrent reading.
• A note on trees, tables, and algorithms
• How to compute digraph width measures on directed co-graphs
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Recognizing hyperelliptic graphs in polynomial time
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Comparing linear width parameters for directed graphs
• Dynamic algorithms for graphs with treewidth 2
• On Dynamic DFS Tree in Directed Graphs
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• Fixed-parameter tractability of treewidth and pathwidth
• The behavior of clique-width under graph operations and graph transformations
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Parameterized algorithms for non-separating trees and branchings in digraphs
• A dynamic data structure for MSO properties in graphs with bounded tree-depth

This page was built for publication: Dynamic algorithms for graphs of bounded treewidth

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