Critical elements in combinatorially closed families of graph classes

DOI10.1134/S1990478917010112zbMath1374.05186MaRDI QIDQ5269161

Dmitriy S. Malyshev

Publication date: 15 June 2017

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

zbMATH Keywords

computational complexityefficient algorithmhereditary classcritical class

Mathematics Subject Classification ID

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

Related Items

On lattice point counting in \(\varDelta\)-modular polyhedra, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, FPT-algorithm for computing the width of a simplex given by a convex hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness results for approximating the bandwidth
• Graph minors. XX: Wagner's conjecture
• Graph minors. V. Excluding a planar graph
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A partial k-arboretum of graphs with bounded treewidth
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Edge dominating set and colorings on graphs with fixed clique-width
• Boundary classes of graphs for the dominating set problem
• The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
• Linear time solvable optimization problems on graphs of bounded clique-width
• Line graphs of bounded clique-width
• NP-hard graph problems and boundary classes of graphs
• Graph Layout Problems Parameterized by Vertex Cover
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Classes of graphs critical for the edge list-ranking problem