Optimal parametric search on graphs of bounded tree-width

DOI10.1007/3-540-58218-5_14zbMath1502.68108OpenAlexW1587940564MaRDI QIDQ5056174

Giora Slutzki, David Fernández Baca

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_14

Mathematics Subject Classification ID

Searching and sorting (68P10) Sensitivity, stability, parametric optimization (90C31) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Using sparsification for parametric minimum spanning tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diameter, width, closest line pair, and parametric searching
• Approximate parametric searching
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Maintaining regular properties dynamically in \(k\)-terminal graphs
• A data structure for dynamic trees
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• Parametric Problems on Graphs of Bounded Tree-Width
• Slowing down sorting networks to obtain faster sorting algorithms
• Linear-time computation of optimal subgraphs of decomposable graphs
• Weighted Multidimensional Search and Its Application to Convex Optimization
• A linear time algorithm for finding tree-decompositions of small treewidth