Boundary graph classes for some maximum induced subgraph problems

DOI10.1007/s10878-012-9529-0zbMath1290.90083OpenAlexW2008836319MaRDI QIDQ2444152

Dmitriy S. Malyshev

Publication date: 8 April 2014

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9529-0

zbMATH Keywords

computational complexityboundary graph classmaximum induced subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boundary properties of graphs for algorithmic graph problems
• The strong perfect graph theorem
• Some simplified NP-complete graph problems
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Boundary classes of graphs for the dominating set problem
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• NP-hard graph problems and boundary classes of graphs
• On maximum planar induced subgraphs
• On the number of boundary classes in the 3-colouring problem
• R(4, 5) = 25
• SPLITTING NUMBER is NP-complete