On the 2-Chain Subgraph Cover and Related Problems

DOI10.1006/JAGM.1994.1034MaRDI QIDQ4312224zbMATH OpenOpenAlexFDO

Authors Tze-Heng Ma, Jeremy P. Spinrad

Publication date 6 November 1994

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1994.1034

zbMATH Keywords

efficient algorithms

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of the k-chain subgraph cover problem
• On maximal chain subgraphs and covers of bipartite graphs
• scientific article; zbMATH DE number 1263242

Cited in

(29)

• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• On the complexity of the k-chain subgraph cover problem
• Induced matchings in asteroidal triple-free graphs
• A min-max property of chordal bipartite graphs with applications
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• A characterization of interval orders with semiorder dimension two
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• A recognition algorithm for simple-triangle graphs
• An intersection model for multitolerance graphs: efficient algorithms and hierarchy
• Vertex splitting and the recognition of trapezoid graphs
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Linear-Interval Dimension and PI Orders
• Graph classes with structured neighborhoods and algorithmic applications
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• An efficient algorithm to solve the conditional covering problem on trapezoid graphs
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• The recognition of triangle graphs
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Line-distortion, bandwidth and path-length of a graph
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• The lexicographic method for the threshold cover problem
• Happy set problem on subclasses of co-comparability graphs
• Intersection of chordal graphs and some related partition problems
• Compact distributed certification of geometric graph classes
• A characterization of uniquely representable two-directional orthogonal ray graphs
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• The induced matching and chain subgraph cover problems for convex bipartite graphs

This page was built for publication: On the 2-Chain Subgraph Cover and Related Problems

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