Minimum weight feedback vertex sets in circle graphs

DOI10.1016/j.ipl.2007.12.003zbMath1185.05077OpenAlexW2038177235MaRDI QIDQ963384

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

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

Related Items

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS, A Faster Algorithm for Maximum Induced Matchings on Circle Graphs, Feedback vertex sets on restricted bipartite graphs, MIP formulations for induced graph optimization problems: a tutorial, Large Induced Subgraphs via Triangulations and CMSO, Parameterized domination in circle graphs, Two Hardness Results on Feedback Vertex Sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• The maximum k-colorable subgraph problem for chordal graphs
• 3D-interval-filament graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• The Complexity of Coloring Circular Arcs and Chords
• Recognition of Circle Graphs
• Feedback vertex set on cocomparability graphs
• Permutation Graphs and Transitive Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Graph-Theoretic Concepts in Computer Science