On the feedback vertex set problem in permutation graphs

DOI10.1016/0020-0190(94)00133-2zbMath0822.68083MaRDI QIDQ1338778

Y. Daniel Liang

Publication date: 9 October 1995

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00133-2

zbMATH Keywords

permutation graph; dynamic programming scheme

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming

Related Items

Unnamed Item, Feedback numbers of Kautz digraphs, Feedback vertex set on AT-free graphs, Feedback numbers of de Bruijn digraphs, Minimum feedback vertex sets in shuffle-based interconnection networks, A linear time algorithm for the minimum weighted feedback vertex set on diamonds, Almost exact minimum feedback vertex set in meshes and butterflies, Feedback vertex sets in mesh-based networks, New upper bounds on feedback vertex numbers in butterflies, Induced Forests in Regular Graphs with Large Girth

Cites Work

• Unnamed Item
• Unnamed Item
• A new approach for the domination problem on permutation graphs
• On domination problems for permutation and other graphs
• An efficient algorithm for maxdominance, with applications
• Finding a minimum independent dominating set in a permutation graph
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• Connected domination and Steiner set on weighted permutation graphs
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• Transitive Orientation of Graphs and Identification of Permutation Graphs