This article is cited in 2 scientific papers (total in 2 papers)
The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
D. S. Malyshevab
a Nizhniy Novgorod State University, Nizhniy Novgorod, Russia
b Nizhniy Novgorod branch of Higher School of Economics, Nizhniy Novgorod, Russia
We completely characterize all hereditary classes defined by at most three forbidden induced subgraphs (obstructions) for which the edge list-ranking problem is polynomial-time solvable. For each class in this family, the algorithm of determining the complexity status of the problem in the class is based on checking whether or not the obstructions belong to some special (“critical”) classes of graphs. The family of such special classes includes, in particular, inclusionwise minimal classes for which the problem is NP-complete. All classes of this type defined by at most three obstructions are described. Ill. 4, bibliogr. 14.
computational complexity, minimal hard class, boundary class, edge list-ranking problem, polynomial algorithm.
PDF file (345 kB)
D. S. Malyshev, “The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions”, Diskretn. Anal. Issled. Oper., 19:1 (2012), 74–96
Citation in format AMSBIB
\paper The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
\jour Diskretn. Anal. Issled. Oper.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Alekseev V.E., Zakharova D.V., Malyshev D.S., Mokeev D.B., Sorochan S.V., “Nekotorye rezultaty o nasledstvennykh klassakh grafov. ii”, Vestnik nizhegorodskogo universiteta im. N.I. Lobachevskogo, 2012, 115–120
D. S. Malyshev, “Critical graph classes for the edge list-ranking problem”, J. Appl. Industr. Math., 8:2 (2014), 245–255
|Number of views:|