scientific article; zbMATH DE number 1420905

MaRDI QIDQ4944974zbMATH OpenFDO

Authors Ljubomir Perković, Bruce Reed

Publication date 8 October 2000

zbMATH Keywords

algorithmtreewidthtree decompositionrooted paths problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph minors (05C83)

Recommendations

• An improved algorithm for finding tree decompositions of small width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Tree-decompositions of small pathwidth
• Tree Decompositions with Small Cost
• Tree decompositions with small cost
• SAT-based local improvement for finding tree decompositions of small width
• Subexponential time algorithms for finding small tree and path decompositions
• scientific article; zbMATH DE number 1222605
• A simple linear-time algorithm for finding path-decompositions of small width
• scientific article; zbMATH DE number 1031380

Cited in

(8)

• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
• Finding good tree decompositions by local search
• Irrelevant vertices for the planar disjoint paths problem
• An Iterative Heuristic Algorithm for Tree Decomposition
• An improved algorithm for finding tree decompositions of small width
• Finding small separators in linear time via treewidth reduction
• Algorithms for solving problems on graphs of bounded pathwidth

This page was built for publication:

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