The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions

zbMATH Open1324.05162MaRDI QIDQ5263762FDOQ5263762

D. S. Malyshev

Publication date: 17 July 2015

Full work available at URL: http://mathnet.ru/eng/da678

Recommendations

• Classes of graphs critical for the edge list-ranking problem
• Minimal hard classes of graphs for the edge list-ranking problem
• The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
• Boundary classes for the list-ranking problems in the case of forests
• On minimal complex classes of graphs

zbMATH Keywords

computational complexitypolynomial algorithmboundary classedge list-ranking problemminimal hard class

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

This page was built for publication: The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5263762)