NP-hard graph problems and boundary classes of graphs
From MaRDI portal
Publication:2465640
DOI10.1016/j.tcs.2007.09.013zbMath1143.68058MaRDI QIDQ2465640
Vadim V. Lozin, Vladimir E. Alekseev, R. Boliac, Dmitry V. Korobitsyn
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
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Boundary Properties of Factorial Classes of Graphs, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, The width and integer optimization on simplices with bounded minors of the constraint matrices, A complexity dichotomy and a new boundary class for the dominating set problem, Boundary properties of well-quasi-ordered sets of graphs, A decidability result for the dominating set problem, \textsc{max-cut} and containment relations in graphs, The coloring problem for classes with two small obstructions, Boundary properties of graphs for algorithmic graph problems, Constant-degree graph expansions that preserve treewidth, On computing the minimum 3-path vertex cover and dissociation number of graphs, On the complexity of the dominating induced matching problem in hereditary classes of graphs, New potential functions for greedy independence and coloring, The \(k\)-path vertex cover of rooted product graphs, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Boundary graph classes for some maximum induced subgraph problems, On the vertex \(k\)-path cover, Boundary properties of the satisfiability problems, A Boundary Property for Upper Domination, max-cut and Containment Relations in Graphs, Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs, Tree-Width and Optimization in Bounded Degree Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Satgraphs and independent domination. I
- The strong perfect graph theorem
- Domination in convex and chordal bipartite graphs
- Recent developments on graphs of bounded clique-width
- Distance-hereditary graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Independent domination in chordal graphs
- Computing independent sets in graphs with large girth
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Alternating cycle-free matchings
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Independent domination in finitely defined classes of 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.
- Some APX-completeness results for cubic graphs
- 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
- Chordal bipartite graphs of bounded tree- and clique-width
- On maximum induced matchings in bipartite graphs
- Boundary classes of graphs for the dominating set problem
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- HAMILTONian circuits in chordal bipartite graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Betweenness, orders and interval graphs
- Totally-Balanced and Greedy Matrices
- Edge Dominating Sets in Graphs
- The NP-Completeness of Edge-Coloring
- Computing the Minimum Fill-In is NP-Complete
- The 3-Colorability Problem on Graphs with Maximum Degree Four
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Hamilton Paths in Grid Graphs
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Characterizations of derived graphs
- On the jump number problem in hereditary classes of bipartite graphs
