On minimal complex classes of graphs

zbMATH Open1249.05368MaRDI QIDQ3115202FDOQ3115202

Authors: D. S. Malyshev 

Publication date: 20 February 2012

Recommendations

• Minimal hard classes of graphs for the edge list-ranking problem
• Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs
• Boundary classes of graphs for some recognition problems
• Boundary classes for the list-ranking problems in the case of forests
• The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions

zbMATH Keywords

computational complexityboundary classlist-ranking problemminimal hard classrecognition of hereditary property

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Cited In (14)

• Title not available (Why is that?)
• On minimal Folkman graphs
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Boundary classes for the list-ranking problems in the case of forests
• Title not available (Why is that?)
• Boundary properties of graphs for algorithmic graph problems
• Minimal hard classes of graphs for the edge list-ranking problem
• 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
• Classes of graphs critical for the edge list-ranking problem
• Critical hereditary graph classes: a survey
• The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
• Minimal Euclidean representations of graphs

This page was built for publication: On minimal complex classes of graphs

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