On the complexity of the k-chain subgraph cover problem

DOI10.1016/S0304-3975(97)00036-4zbMath0913.68004MaRDI QIDQ1275070

Tze-Heng Ma, Gen-Huey Chen, Chang Wu Yu

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

bipartite graphcomparability graphconvex bipartite graphparallel random access machineNC classP class

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Related Items (7)

Induced matchings in asteroidal triple-free graphs ⋮ A min-max property of chordal bipartite graphs with applications ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ On Maximal Chain Subgraphs and Covers of Bipartite Graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination in convex and chordal bipartite graphs
• Multidimensional scaling and threshold graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Parallel recognition of the consecutive ones property with applications
• The Complexity of the Partial Order Dimension Problem
• Parallel Merge Sort
• Node-Deletion Problems on Bipartite Graphs
• Covering the edges with consecutive sets
• On the 2-Chain Subgraph Cover and Related Problems
• Maximum matching in a convex bipartite graph
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: On the complexity of the k-chain subgraph cover problem