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

zbMATH Open1324.05162MaRDI QIDQ5263762FDOQ5263762

Authors: 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)

Cited In (5)

• Boundary classes for the list-ranking problems in the case of forests
• Minimal hard classes of graphs for the edge list-ranking problem
• Graph classes and forbidden patterns on three vertices
• On minimal complex classes of graphs
• Classes of graphs critical for the edge list-ranking problem

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)