Minimum weight feedback vertex sets in circle graphs

DOI10.1016/J.IPL.2007.12.003MaRDI QIDQ963384zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 19 April 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2007.12.003

zbMATH Keywords

graph algorithmscircle graphmaximum induced forestminimum feedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Signed and weighted graphs (05C22)

Recommendations

• Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• An algorithm to find a minimum feedback vertex set of an interval graph
• Feedback vertex set on AT-free graphs
• A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• 3D-interval-filament graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An algorithm to find a minimum feedback vertex set of an interval graph
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Feedback vertex set on cocomparability graphs
• Graph-Theoretic Concepts in Computer Science
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Permutation Graphs and Transitive Graphs
• Recognition of Circle Graphs
• The Complexity of Coloring Circular Arcs and Chords
• The maximum k-colorable subgraph problem for chordal graphs

Cited in

(12)

• Parameterized domination in circle graphs
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Feedback vertex set on AT-free graphs
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
• An algorithm to find a minimum feedback vertex set of an interval graph
• MIP formulations for induced graph optimization problems: a tutorial
• Circular convex bipartite graphs: feedback vertex set
• Feedback vertex sets on restricted bipartite graphs
• Two Hardness Results on Feedback Vertex Sets
• Circular convex bipartite graphs: feedback vertex sets
• Large Induced Subgraphs via Triangulations and CMSO

This page was built for publication: Minimum weight feedback vertex sets in circle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963384)