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

MaRDI QIDQ5263762zbMATH OpenFDO

Authors D. S. Malyshev

Publication date 17 July 2015

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

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)

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

Cited in

(5)

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

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)