Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs

MaRDI QIDQ1920227zbMATH OpenFDO

Authors Y. Daniel Liang, Maw-Shang Chang

Publication date 19 June 1997

Published in Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

cocomparability graphspolynomial-time algorithmsfeedback vertex setcomplex bipartite graphs

Mathematics Subject Classification ID

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

Cited in

(31)

• Maximum bipartite subgraphs of geometric intersection graphs
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• Minimum feedback vertex sets in shuffle-based interconnection networks
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• New upper bounds on feedback vertex numbers in butterflies
• On the Complexity of Singly Connected Vertex Deletion
• Feedback vertex set in hypercubes
• Circular convex bipartite graphs: feedback vertex sets
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Feedback vertex sets on restricted bipartite graphs
• Degenerate matchings and edge colorings
• Feedback vertex set on AT-free graphs
• scientific article; zbMATH DE number 5492392 (Why is no real title available?)
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Feedback vertex sets in star graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Almost exact minimum feedback vertex set in meshes and butterflies
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Feedback vertex sets in mesh-based networks
• Connected feedback vertex set on AT-free graphs
• The integrity of a cubic graph
• Decycling bipartite graphs
• Finding maximum edge bicliques in convex bipartite graphs
• Connected feedback vertex set on AT-free graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• On the complexity of singly connected vertex deletion
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Feedback vertex set on cocomparability graphs
• Approximation hardness of domination problems on generalized convex graphs
• scientific article; zbMATH DE number 2230267 (Why is no real title available?)

This page was built for publication: Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920227)