On the 2-Chain Subgraph Cover and Related Problems
From MaRDI portal
Publication:4312224
DOI10.1006/jagm.1994.1034zbMath0821.68097OpenAlexW1972965975MaRDI QIDQ4312224
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (27)
A linear time algorithm for finding depth-first spanning trees on trapezoid graphs ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ A recognition algorithm for simple-triangle graphs ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Linear-Interval Dimension and PI Orders ⋮ An efficient algorithm to solve the conditional covering problem on trapezoid graphs ⋮ Induced matchings in asteroidal triple-free graphs ⋮ The recognition of triangle graphs ⋮ A min-max property of chordal bipartite graphs with applications ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ The lexicographic method for the threshold cover problem ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ A characterization of interval orders with semiorder dimension two ⋮ Vertex splitting and the recognition of trapezoid graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ On the complexity of the k-chain subgraph cover problem ⋮ The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
This page was built for publication: On the 2-Chain Subgraph Cover and Related Problems
