Open AccessPartitioning a split graph into induced subgraphs isomorphic to the path of order 3.
Author(s) -
О. И. Дугинов
Publication year - 2019
Publication title -
vescì nacyânalʹnaj akadèmìì navuk belarusì. seryâ fìzìka-matèmatyčnyh navuk
Language(s) - English
Resource type - Journals
eISSN - 2524-2415
pISSN - 1561-2430
DOI - 10.29235/1561-2430-2019-55-1-32-49
Subject(s) - combinatorics , vertex (graph theory) , mathematics , time complexity , graph , discrete mathematics , computational complexity theory , longest path problem , computer science , theoretical computer science , algorithm , chordal graph
The study of the computational complexity of problems on graphs is an urgent problem. We show that the problem of deciding whether the vertex set of a given split graph of order 3n can be partitioned into induced subgraphs isomorphic to P3 is a polynomially solvable problem. We develop a polynomial-time algorithm based on the method of augmenting graphs. The developed efficient algorithm can be used for solving team formation problems.