NP-hard graph problems and boundary classes of graphs

DOI10.1016/J.TCS.2007.09.013zbMATH Open1143.68058OpenAlexW2081207138MaRDI QIDQ2465640FDOQ2465640

Authors: R. Boliac, Dmitry V. Korobitsyn, Vadim Lozin, V. E. Alekseev 

Publication date: 7 January 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.09.013

Recommendations

• Boundary classes of graphs for the dominating set problem
• Boundary classes of graphs for some recognition problems
• Boundary classes for graph problems involving non-local properties
• Boundary graph classes for some maximum induced subgraph problems
• Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs

zbMATH Keywords

computational complexityhereditary class of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Some APX-completeness results for cubic graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Boundary classes of graphs for the dominating set problem
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Linear time solvable optimization problems on graphs of bounded clique-width
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Hamilton Paths in Grid Graphs
• On the clique-width of some perfect graph classes
• Characterizations of derived graphs
• The strong perfect graph theorem
• Recent developments on graphs of bounded clique-width
• Distance-hereditary graphs
• On maximum induced matchings in bipartite graphs
• HAMILTONian circuits in chordal bipartite graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Domination in convex and chordal bipartite graphs
• Edge Dominating Sets in Graphs
• Totally-Balanced and Greedy Matrices
• Computing the Minimum Fill-In is NP-Complete
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Independent domination in chordal graphs
• Betweenness, orders and interval graphs
• Title not available (Why is that?)
• Computing independent sets in graphs with large girth
• Title not available (Why is that?)
• Independent domination in finitely defined classes of graphs
• Chordal bipartite graphs of bounded tree- and clique-width
• Title not available (Why is that?)
• Satgraphs and independent domination. I
• Alternating cycle-free matchings
• On the jump number problem in hereditary classes of bipartite graphs

Cited In (55)

• The maximum number of maximum dissociation sets in trees
• Maximum dissociation sets in subcubic trees
• Title not available (Why is that?)
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Computing coverage kernels under restricted settings
• Vertex coloring of graphs with few obstructions
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• Critical properties of bipartite permutation graphs
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Critical elements in combinatorially closed families of graph classes
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Boundary Classes of Planar Graphs
• Constant-degree graph expansions that preserve treewidth
• The \(k\)-path vertex cover of rooted product graphs
• Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
• Upper domination: towards a dichotomy through boundary properties
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• \textsc{max-cut} and containment relations in graphs
• Max-Cut and containment relations in graphs
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Boundary classes of graphs for the dominating set problem
• On universally easy classes for NP-complete problems
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• Boundary classes for graph problems involving non-local properties
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• A boundary property for upper domination
• Boundary graph classes for some maximum induced subgraph problems
• On the vertex \(k\)-path cover
• Boundary properties of the satisfiability problems
• A boundary class for the \(k\)-path partition problem
• Boundary classes of graphs for some recognition problems
• A decidability result for the dominating set problem
• Nearest neighbour graph realizability is NP-hard
• NP-hardness of multiple bondage in graphs
• New potential functions for greedy independence and coloring
• Two complexity results for the vertex coloring problem
• Tree-Width and Optimization in Bounded Degree Graphs
• Boundary properties of factorial classes of graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Boundary properties of well-quasi-ordered sets of graphs
• A \(5k\)-vertex kernel for 3-path vertex cover
• The maximum number of maximum generalized 4-independent sets in trees
• Extremal vertex-degree function index with given order and dissociation number
• On spectral extrema of graphs with given order and dissociation number
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• On the \(A_\alpha\)-index of graphs with given order and dissociation number

This page was built for publication: NP-hard graph problems and boundary classes of graphs

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