NP-hard graph problems and boundary classes of graphs

DOI10.1016/J.TCS.2007.09.013MaRDI QIDQ2465640zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(55)

• The maximum number of maximum dissociation sets in trees
• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Maximum dissociation sets in subcubic trees
• 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
• Vertex coloring of graphs with few obstructions
• scientific article; zbMATH DE number 7742925 (Why is no real title available?)
• Computing coverage kernels under restricted settings
• Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• Critical properties of bipartite permutation graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• Critical elements in combinatorially closed families of graph classes
• 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
• \textsc{max-cut} and containment relations in graphs
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• The maximum number of maximum generalized 4-independent sets in trees
• Max-Cut and containment relations in graphs
• Boundary classes of graphs for the dominating set problem
• On universally easy classes for NP-complete problems
• On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Boundary classes for graph problems involving non-local properties
• Extremal vertex-degree function index with given order and dissociation number
• On spectral extrema of graphs with given order and dissociation number
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• 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
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• A decidability result for the dominating set problem
• On the \(A_\alpha\)-index of graphs with given order and dissociation number
• NP-hardness of multiple bondage in graphs
• Nearest neighbour graph realizability is NP-hard
• New potential functions for greedy independence and coloring
• Two complexity results for the vertex coloring problem
• Tree-Width and Optimization in Bounded Degree Graphs
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Boundary properties of factorial classes of graphs
• Boundary properties of well-quasi-ordered sets of graphs
• A \(5k\)-vertex kernel for 3-path vertex cover

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)