𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

✍ Scribed by B. Courcelle; J. A. Makowsky; U. Rotics

Book ID
105915367
Publisher
Springer
Year
2000
Tongue
English
Weight
150 KB
Volume
33
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David FernΓ‘ndez-Baca; Giora Slutzki πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

On approximability of linear ordering an
On approximability of linear ordering and related NP-optimization problems on graphs
✍ Sounaka Mishra; Kripasindhu Sikdar πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 337 KB

We investigate the approximability of minimum and maximum linear ordering problems (MIN-LOP and MAX-LOP) and related feedback set problems such as maximum weight acyclic subdiagraph (MAX-W-SUBDAG), minimum weight feedback arc/vertex set (MIN-W-FAS/ MIN-W-FVS) and a generalization of the latter calle