Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs (Q2118390): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00453-021-00904-w / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2769128044 / rank
 
Normal rank
Property / cites work
 
Property / cites work: NP-completeness results for some problems on subclasses of bipartite and chordal graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: The induced matching and chain subgraph cover problems for convex bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum induced matchings for chordal graphs in linear time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Induced matchings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding a maximum induced matching in weakly chordal graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Induced matchings in asteroidal triple-free graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Covering the edges with consecutive sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the approximability of the maximum induced matching problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: An 0(n log n) algorithm for the convex bipartite matching problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum matching in a convex bipartite graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: New results on induced matchings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Difference graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-time algorithm for the paired-domination problem in convex bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Matchings in Node-Weighted Convex Bipartite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size / rank
 
Normal rank
Property / cites work
 
Property / cites work: On maximum induced matchings in bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Certifying algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: HAMILTONian circuits in chordal bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum weight induced matching in some subclasses of bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Induced Matching in Some Subclasses of Bipartite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithms for maximum independent set in convex bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient graph representations / rank
 
Normal rank
Property / cites work
 
Property / cites work: A linear time algorithm for maximum matchings in convex, bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: NP-completeness of some generalizations of the maximum matching problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of the k-chain subgraph cover problem / rank
 
Normal rank

Latest revision as of 09:53, 28 July 2024

scientific article
Language Label Description Also known as
English
Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
scientific article

    Statements

    Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs (English)
    0 references
    0 references
    0 references
    0 references
    22 March 2022
    0 references
    graph algorithm
    0 references
    induced matching
    0 references
    chain cover
    0 references
    convex bipartite graph
    0 references
    certifying algorithm
    0 references
    dynamic programming
    0 references
    0 references
    0 references
    0 references

    Identifiers