๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A linear-time algorithm for the weighted feedback vertex problem on interval graphs

โœ Scribed by Chin Lung Lu; Chuan Yi Tang

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
459 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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-independent set problem are equivalent on chordal graphs, we can solve the latter three problems in linear-time on interval graphs, too. @ 1997 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

A linear time recognition algorithm for
A linear time recognition algorithm for proper interval graphs
โœ B.S. Panda; Sajal K. Das ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 128 KB

We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian

Linear-time certifying algorithms for th
Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
โœ Ruo-Wei Hung; Maw-Shang Chang ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 252 KB

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appear