Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs

zbMATH Open0865.68086MaRDI QIDQ1920227FDOQ1920227

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
• New upper bounds on feedback vertex numbers in butterflies
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• On the Complexity of Singly Connected Vertex Deletion
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Feedback vertex set in hypercubes
• Circular convex bipartite graphs: feedback vertex sets
• Degenerate matchings and edge colorings
• Feedback vertex sets on restricted bipartite graphs
• Feedback vertex set on AT-free graphs
• Title not available (Why is that?)
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Feedback vertex sets in star graphs
• Almost exact minimum feedback vertex set in meshes and butterflies
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Subset feedback vertex set on graphs of bounded independent set size
• Subset feedback vertex set on graphs of bounded independent set size
• Connected feedback vertex set on AT-free graphs
• Feedback vertex sets in mesh-based networks
• The integrity of a cubic graph
• Decycling bipartite graphs
• Connected feedback vertex set on AT-free graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• Finding maximum edge bicliques in convex bipartite 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
• Title not available (Why is that?)

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)