Algorithms for the Recognition of Net-free Graphs and for Computing Maximum Cardinality Matchings in Claw-free Graphs | Zendy

Mihai Tălmaciu | Zendy; Victor Lepin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Algorithms for the Recognition of Net-free Graphs and for Computing Maximum Cardinality Matchings in Claw-free Graphs

Author(s) -

Mihai Tălmaciu,

Victor Lepin

Publication year - 2014

Publication title -

studies in informatics and control

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.321

H-Index - 22

eISSN - 1841-429X

pISSN - 1220-1766

DOI - 10.24846/v23i2y201406

Subject(s) - chordal graph , combinatorics , computer science , pathwidth , indifference graph , cograph , modular decomposition , partition (number theory) , cardinality (data modeling) , claw , maximal independent set , split graph , net (polyhedron) , mathematics , graph , discrete mathematics , line graph , 1 planar graph , data mining , geometry , mechanical engineering , engineering

During the last decades, numerous studies have been undertaken on the classes of net-free graphs, claw-free graphs, and the relationship between them. The notion of weakly decomposition (a partition of the set of vertices in three classes A, B, C such that A induces a connected graph and C is totally adjacent to B and totally non-adjacent to A) and the study of its properties allow us to obtain several important results such as: characterization of cographs, {P4,C4}-free and paw-free graphs. In this article, we give a characterization of net-free graphs, a characterization of claw-free graphs, using weakly decomposition. Also, we give a recognition algorithm for net-free graphs, an algorithm for determining a maximum matching in claw-free graphs, comparable with existing algorithms in terms of complexity, but using weakly decomposition.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research