On the Feedback Vertex set Problem in Permutation Graphs

Y. Daniel Liang

doi:10.1016/0020-0190(94)00133-2

On the Feedback Vertex set Problem in Permutation Graphs

Y. Daniel Liang

Computer Science

Indiana Purdue Univ at Fort Wayne

Research output: Contribution to journal › Article › peer-review

61 Scopus citations

Abstract

Brandstädt and Kratsch (1987) presented an O( n 6 ) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.m̄ ) by Brandstät (1993), where m̄ is the number of edges in the complement of G . In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O( nm ) for this problem in permutation graphs.

Original language	American English
Journal	Information Processing Letters
Volume	52
DOIs	https://doi.org/10.1016/0020-0190(94)00133-2
State	Published - Nov 11 1994

Disciplines

Computer Sciences

Keywords

Algorithms
Minimum weight feedback vertex set
Permutation graph

Access to Document

10.1016/0020-0190(94)00133-2License: Unspecified

Cite this

@article{e4f47a6d29794fcb93fea4bf5fcfbe5e,

title = "On the Feedback Vertex set Problem in Permutation Graphs",

abstract = " Brandst{\"a}dt and Kratsch (1987) presented an O( n 6 ) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.{\=m} ) by Brandst{\"a}t (1993), where {\=m} is the number of edges in the complement of G . In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O( nm ) for this problem in permutation graphs. ",

keywords = "Algorithms, Minimum weight feedback vertex set, Permutation graph",

author = "{Daniel Liang}, Y.",

note = "Brandst{\"a}dt and Kratsch (1987) presented an O( n 6) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.{\=m}) by Brandst{\"a}t (1993), where {\=m} is the number of edges in the complement of G.",

year = "1994",

month = nov,

day = "11",

doi = "10.1016/0020-0190(94)00133-2",

language = "American English",

volume = "52",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the Feedback Vertex set Problem in Permutation Graphs

AU - Daniel Liang, Y.

N1 - Brandstädt and Kratsch (1987) presented an O( n 6) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.m̄) by Brandstät (1993), where m̄ is the number of edges in the complement of G.

PY - 1994/11/11

Y1 - 1994/11/11

N2 - Brandstädt and Kratsch (1987) presented an O( n 6 ) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.m̄ ) by Brandstät (1993), where m̄ is the number of edges in the complement of G . In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O( nm ) for this problem in permutation graphs.

AB - Brandstädt and Kratsch (1987) presented an O( n 6 ) time algorithm for the minimum weight feedback vertex set problem in a permutation graph of n vertices and m edges. This result was recently improved to O( n.m.m̄ ) by Brandstät (1993), where m̄ is the number of edges in the complement of G . In this paper, we employ a different dynamic programming scheme to reduce the time complexity to O( nm ) for this problem in permutation graphs.

KW - Algorithms

KW - Minimum weight feedback vertex set

KW - Permutation graph

UR - https://www.sciencedirect.com/science/article/pii/0020019094001332

U2 - 10.1016/0020-0190(94)00133-2

DO - 10.1016/0020-0190(94)00133-2

M3 - Article

SN - 0020-0190

VL - 52

JO - Information Processing Letters

JF - Information Processing Letters

ER -

On the Feedback Vertex set Problem in Permutation Graphs

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this