MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS

DOI10.1142/S1793830911001243zbMath1242.05261OpenAlexW2057789585MaRDI QIDQ2890989

Fanica Gavril

Publication date: 12 June 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830911001243

zbMATH Keywords

polygon-circle graphcircle graphmaximum induced forestminimum feedback vertex setcircle trapezoid graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

Large Induced Subgraphs via Triangulations and CMSO

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Trapezoid graphs and generalizations, geometry and algorithms
• Feedback vertex set on AT-free graphs
• Minimum weight feedback vertex sets in circle graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Thresholds for classes of intersection graphs
• 3D-interval-filament graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• The Complexity of Coloring Circular Arcs and Chords
• Feedback vertex set on cocomparability graphs

This page was built for publication: MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS