Boundary graph classes for some maximum induced subgraph problems
From MaRDI portal
Publication:2444152
DOI10.1007/S10878-012-9529-0zbMATH Open1290.90083OpenAlexW2008836319MaRDI QIDQ2444152FDOQ2444152
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
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
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Graph theory
- Graph theory
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Boundary classes of graphs for the dominating set problem
- NP-hard graph problems and boundary classes of graphs
- Continuous sets of the boundary classes of graphs for coloring problems
- Boundary properties of graphs for algorithmic graph problems
- Title not available (Why is that?)
- The strong perfect graph theorem
- Some simplified NP-complete graph problems
- Boundary classes of graphs for some recognition problems
- Title not available (Why is that?)
- R(4, 5) = 25
- On the number of boundary classes in the 3-colouring problem
- Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
- On maximum planar induced subgraphs
- SPLITTING NUMBER is NP-complete
- Title not available (Why is that?)
Cited In (8)
- A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
- Critical elements in combinatorially closed families of graph classes
- 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
- On lattice point counting in \(\varDelta\)-modular polyhedra
- NP-hard graph problems and boundary classes of graphs
- Boundary classes of graphs for some recognition problems
- On \(\Delta\)-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)
