𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

✍ Scribed by Hans L. Bodlaender; Fedor V. Fomin; Arie M. C. A. Koster; Dieter Kratsch; Dimitrios M. Thilikos

Publisher
Springer
Year
2011
Tongue
English
Weight
446 KB
Volume
50
Category
Article
ISSN
1433-0490

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Algorithms for vertex-partitioning probl
Algorithms for vertex-partitioning problems on graphs with fixed clique-width
✍ Michael U. Gerber; Daniel Kobler πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 189 KB

Many vertex-partitioning problems can be expressed within a general framework introduced by Telle and Proskurowski. They showed that optimization problems in this framework can be solved in polynomial time on classes of graphs with bounded tree-width. In this paper, we consider a very similar framew

A note on vertex pancyclic oriented grap
A note on vertex pancyclic oriented graphs
✍ Bang-Jensen, JοΏ½rgen; Guo, Yubao πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 185 KB πŸ‘ 2 views

Let D be an oriented graph of order n β‰₯ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

A note on vertex orders for stability nu
A note on vertex orders for stability number
✍ Mahadev, N. V. R.; Reed, B. A. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 115 KB πŸ‘ 2 views

We investigate vertex orders that can be used to obtain maximum stable sets by a simple greedy algorithm in polynomial time in some classes of graphs. We characterize a class of graphs for which the stability number can be obtained by a simple greedy algorithm. This class properly contains previousl

A linear-time algorithm for the weighted
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
✍ Chin Lung Lu; Chuan Yi Tang πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 459 KB

We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3.1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-indepe