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

DOI10.1016/S0020-0190(96)00193-7zbMath1336.68140OpenAlexW2011576340MaRDI QIDQ286981

Chin Lung Lu, Chuan Yi Tang

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(96)00193-7

zbMATH Keywords

interval graphs\(C_{3, 1}\) problem2-colorable subgraph problem2-independent set problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

The size of graphs with given feedback vertex number ⋮ Feedback vertex set in hypercubes ⋮ A feedback vertex set of 2-degenerate graphs ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Feedback vertex sets in mesh-based networks ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Almost exact minimum feedback vertex set in meshes and butterflies ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Domination number and feedback vertex number of complements of line graphs ⋮ Complexity of maximum cut on interval graphs ⋮ Connected feedback vertex set on AT-free graphs ⋮ Degenerate matchings and edge colorings ⋮ Solving the feedback vertex set problem on undirected graphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Feedback vertex set on AT-free graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Minimum feedback vertex sets in shuffle-based interconnection networks ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Feedback vertex sets in star graphs ⋮ The integrity of a cubic graph ⋮ A linear time algorithm for the minimum weighted feedback vertex set on diamonds ⋮ New bounds on the size of the minimum feedback vertex set in meshes and butterflies. ⋮ Minimum feedback vertex set and acyclic coloring. ⋮ Minimum Weighted Feedback Vertex Set on Diamonds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(K_ i\)-covers. I: Complexity and polytopes
• On domination problems for permutation and other graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Generalized vertex covering in interval graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Maximum \(k\)-covering of weighted transitive graphs with applications
• The complexity of generalized clique covering
• On the feedback vertex set problem in permutation graphs
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithms for maximumk-colorings andk-coverings of transitive graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Node-Deletion Problems on Bipartite Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: A linear-time algorithm for the weighted feedback vertex problem on interval graphs