Approximating treewidth, pathwidth, and minimum elimination tree height

DOI10.1007/3-540-55121-2_1MaRDI QIDQ4694712zbMATH OpenFDO

Authors J. R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks, Hans L. Bodlaender

Publication date 29 June 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/17927

zbMATH Keywords

algorithm of Leightonapproximation algorithmsminimum elimination tree heightminimum front sizepathwidthsparse matrix factorizationtreewidthvertex separators

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• An improvement of Reed's treewidth approximation
• Approximation algorithms for treewidth
• On treewidth approximations.
• On treewidth approximations

Cited in

(22)

• AND/OR search spaces for graphical models
• AND/OR branch-and-bound search for combinatorial optimization in graphical models
• An optimal parallel algorithm for node ranking of cographs
• Triangulating multitolerance graphs
• On vertex ranking of a starlike graph
• \(l_p\)-optimal rankings and max-optimal rankings are different
• Triangulating graphs without asteroidal triples
• Space saving by dynamic algebraization based on tree-depth
• Parameterized complexity of fair feedback vertex set problem
• Search-space size in contraction hierarchies
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Metric Embedding via Shortest Path Decompositions
• Parameterization of tensor network contraction
• To approximate treewidth, use treelength!
• Rankings of graphs
• Vertex ranking of asteroidal triple-free graphs
• Graphs whose \(l_p\)-optimal rankings are \(l_{\infty}\) optimal
• Faster parameterized algorithms for modification problems to minor-closed classes
• Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
• Mixed deterministic and probabilistic networks
• Approximation algorithms for treewidth
• Constructing a minimum height elimination tree of a tree in linear time

This page was built for publication: Approximating treewidth, pathwidth, and minimum elimination tree height

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