On the 2-Chain Subgraph Cover and Related Problems

DOI10.1006/jagm.1994.1034zbMath0821.68097MaRDI QIDQ4312224

Jeremy P. Spinrad, Tze-Heng Ma

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

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

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, The recognition of triangle graphs, Efficient algorithms for the minimum connected domination on trapezoid graphs, The induced matching and chain subgraph cover problems for convex bipartite graphs, 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, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, Vertex splitting and the recognition of trapezoid graphs, An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs, Linear-Interval Dimension and PI Orders, An efficient algorithm to generate all maximal independent sets on trapezoid graphs