Classes of graphs critical for the edge list-ranking problem

DOI10.1134/S1990478914020112zbMATH Open1324.05163MaRDI QIDQ5264719FDOQ5264719

D. S. Malyshev

Publication date: 27 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Recommendations

• Minimal hard classes of graphs for the edge list-ranking problem
• The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
• Boundary classes for the list-ranking problems in the case of forests
• On minimal complex classes of graphs
• scientific article

zbMATH Keywords

computational complexityhereditary classpolynomial algorithmboundary classedge list-ranking problemminimal hard class

Mathematics Subject Classification ID

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

Cited In (12)

• Title not available (Why is that?)
• Critical elements in combinatorially closed families of graph classes
• On integer programming with bounded determinants
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• On lattice point counting in \(\varDelta\)-modular polyhedra
• FPT-algorithm for computing the width of a simplex given by a convex hull
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• On König graphs with respect to P4
• Optimal edge ranking of complete bipartite graphs in polynomial time
• Edge ranking of graphs is hard

This page was built for publication: Classes of graphs critical for the edge list-ranking problem

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