Feedback vertex set on AT-free graphs

DOI10.1016/j.dam.2007.10.006zbMath1152.68044OpenAlexW2129287737MaRDI QIDQ944750

Dieter Kratsch, Ioan Todinca, Haiko Müller

Publication date: 10 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.10.006

zbMATH Keywords

feedback vertex setasteroidal triple-free graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Faster exact algorithms for some terminal set problems, MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS, Unnamed Item, Connected feedback vertex set on AT-free graphs, Unnamed Item, Degenerate matchings and edge colorings, Subset feedback vertex sets in chordal graphs, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Proper Interval Vertex Deletion, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Mim-width. II. The feedback vertex set problem, Subset feedback vertex set on graphs of bounded independent set size, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• On domination problems for permutation and other graphs
• On the feedback vertex set problem in permutation graphs
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Efficient graph representations
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Wavelength Conversion in Optical Networks
• Independent Sets in Asteroidal Triple-Free Graphs
• Asteroidal Triple-Free Graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Depth-First Search and Linear Graph Algorithms
• On the structure of graphs with bounded asteroidal number