On the feedback vertex set problem in permutation graphs

DOI10.1016/0020-0190(94)00133-2zbMath0822.68083OpenAlexW2089749235MaRDI 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 graphdynamic programming scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items

On the Complexity of Singly Connected Vertex Deletion, A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Feedback vertex set in hypercubes, Feedback vertex sets in mesh-based networks, New upper bounds on feedback vertex numbers in butterflies, The decycling number of $P_{m} \square P_{n}^{\ast}$, Feedback numbers of Kautz digraphs, Almost exact minimum feedback vertex set in meshes and butterflies, New bounds on the decycling number of generalized de Bruijn digraphs, Connected feedback vertex set on AT-free graphs, Degenerate matchings and edge colorings, On the decycling number of generalized Kautz digraphs, Induced Forests in Regular Graphs with Large Girth, Feedback vertex set on AT-free graphs, Feedback numbers of de Bruijn digraphs, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, Minimum feedback vertex sets in shuffle-based interconnection networks, Feedback arc number and feedback vertex number of Cartesian product of directed cycles, Unnamed Item, A linear time algorithm for the minimum weighted feedback vertex set on diamonds, On the complexity of singly connected vertex deletion

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