Boundary graph classes for some maximum induced subgraph problems

DOI10.1007/S10878-012-9529-0MaRDI QIDQ2444152zbMATH OpenOpenAlexFDO

Authors D. 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

boundary graph classcomputational complexitymaximum induced subgraph problem

Mathematics Subject Classification ID

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

Recommendations

• Boundary classes of graphs for the dominating set problem
• The maximum degree \& diameter-bounded subgraph and its applications
• On maximum planar induced subgraphs
• Bounds and extrema for classes of graphs and finite structures
• scientific article; zbMATH DE number 6004968
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Boundary classes of graphs for some recognition problems
• scientific article; zbMATH DE number 812041
• The maximum happy induced subgraph problem: bounds and algorithms
• NP-hard graph problems and boundary classes of graphs

Cites work

• R(4, 5) = 25
• Boundary classes of graphs for some recognition problems
• Boundary classes of graphs for the dominating set problem
• Boundary properties of graphs for algorithmic graph problems
• Continuous sets of the boundary classes of graphs for coloring problems
• Graph theory
• Graph theory
• scientific article; zbMATH DE number 6004968 (Why is no real title available?)
• scientific article; zbMATH DE number 6004976 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• NP-hard graph problems and boundary classes of graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• On maximum planar induced subgraphs
• On the number of boundary classes in the 3-colouring problem
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• Some simplified NP-complete graph problems
• SPLITTING NUMBER is NP-complete
• The strong perfect graph theorem

Cited in

(8)

• On lattice point counting in -modular polyhedra
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• Boundary classes for graph problems involving non-local properties
• NP-hard graph problems and boundary classes of graphs
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Boundary classes of graphs for some recognition problems
• Critical elements in combinatorially closed families of graph classes
• On -modular integer linear problems in the canonical form and equivalent problems

This page was built for publication: Boundary graph classes for some maximum induced subgraph problems

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