Boundary classes for graph problems involving non-local properties (Q2401761): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2017.06.012
+Normal rank
@@ Property / OpenAlex ID @@
+W2731362769
@@ Property / OpenAlex ID: W2731362769 / rank @@
+Normal rank
@@ Property / cites work @@
+A Dichotomy for Upper Domination in Monogenic Classes
+Normal rank
@@ Property / cites work @@
+Q3888545
@@ Property / cites work: Q3888545 / rank @@
+Normal rank
@@ Property / cites work @@
+On easy and hard hereditary classes of graphs with respect to the independent set problem
+Normal rank
@@ Property / cites work @@
+Q3115709
@@ Property / cites work: Q3115709 / rank @@
+Normal rank
@@ Property / cites work @@
+Boundary classes of graphs for the dominating set problem
+Normal rank
@@ Property / cites work @@
+NP-hard graph problems and boundary classes of graphs
+Normal rank
@@ Property / cites work @@
+Easy problems for tree-decomposable graphs
@@ Property / cites work: Easy problems for tree-decomposable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Feedback vertex set on graphs of low clique-width
@@ Property / cites work: Feedback vertex set on graphs of low clique-width / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of generalized clique covering
@@ Property / cites work: The complexity of generalized clique covering / rank @@
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+Upper bounds to the clique width of graphs
@@ Property / cites work: Upper bounds to the clique width of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Handle-rewriting hypergraph grammars
@@ Property / cites work: Handle-rewriting hypergraph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time solvable optimization problems on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / rank @@
+Normal rank
@@ Property / cites work @@
+NP-completeness and degree restricted spanning trees
+Normal rank
@@ Property / cites work @@
+On Hadwiger's Number and the Stability Number
@@ Property / cites work: On Hadwiger's Number and the Stability Number / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
+Normal rank
@@ Property / cites work @@
+Vertex and edge covers with clustering properties: Complexity and algorithms
+Normal rank
@@ Property / cites work @@
+Exact exponential algorithms.
@@ Property / cites work: Exact exponential algorithms. / rank @@
+Normal rank
@@ Property / cites work @@
+An augmenting path algorithm for linear matroid parity
+Normal rank
@@ Property / cites work @@
+The Rectilinear Steiner Tree Problem is $NP$-Complete
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Feedback vertex sets in cubic multigraphs
@@ Property / cites work: Feedback vertex sets in cubic multigraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Closing complexity gaps for coloring problems on \(H\)-free graphs
+Normal rank
@@ Property / cites work @@
+A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
+Normal rank
@@ Property / cites work @@
+A weighted linear matroid parity algorithm
@@ Property / cites work: A weighted linear matroid parity algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+\textsc{max-cut} and containment relations in graphs
+Normal rank
@@ Property / cites work @@
+Recent developments on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Boundary properties of graphs for algorithmic graph problems
+Normal rank
@@ Property / cites work @@
+Q4448764
@@ Property / cites work: Q4448764 / rank @@
+Normal rank
@@ Property / cites work @@
+The VC-dimension of set systems defined by graphs
@@ Property / cites work: The VC-dimension of set systems defined by graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A new bound on the feedback vertex sets in cubic graphs
+Normal rank
@@ Property / cites work @@
+Independent Set in <i>P</i><sub>5</sub>-Free Graphs in Polynomial Time
+Normal rank
@@ Property / cites work @@
+Independence and Efficient Domination on <i>P</i><sub>6</sub>-free Graphs
+Normal rank
@@ Property / cites work @@
+Matroid matching and some applications
@@ Property / cites work: Matroid matching and some applications / rank @@
+Normal rank
@@ Property / cites work @@
+Matching theory
@@ Property / cites work: Matching theory / rank @@
+Normal rank
@@ Property / cites work @@
+On the maximum independent set problem in subclasses of subcubic graphs
+Normal rank
@@ Property / cites work @@
+Q3115195
@@ Property / cites work: Q3115195 / rank @@
+Normal rank
@@ Property / cites work @@
+Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
+Normal rank
@@ Property / cites work @@
+A complexity dichotomy and a new boundary class for the dominating set problem
+Normal rank
@@ Property / cites work @@
+Critical hereditary graph classes: a survey
@@ Property / cites work: Critical hereditary graph classes: a survey / rank @@
+Normal rank
@@ Property / cites work @@
+On maximal independent sets of vertices in claw-free graphs
+Normal rank
@@ Property / cites work @@
+HAMILTONian circuits in chordal bipartite graphs
@@ Property / cites work: HAMILTONian circuits in chordal bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
+Normal rank
@@ Property / cites work @@
+The VC-dimension of graphs with respect to \(k\)-connected subgraphs
+Normal rank
@@ Property / cites work @@
+On line graphs of subcubic triangle-free graphs
@@ Property / cites work: On line graphs of subcubic triangle-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Fast, Simpler Algorithm for the Matroid Parity Problem
+Normal rank
@@ Property / cites work @@
+Approximating clique-width and branch-width
@@ Property / cites work: Approximating clique-width and branch-width / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of Tutte invariants of 2-polymatroids
+Normal rank
@@ Property / cites work @@
+On limited nondeterminism and the complexity of the V-C dimension
+Normal rank
@@ Property / cites work @@
+The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
+Normal rank
@@ Property / cites work @@
+Q3318125
@@ Property / cites work: Q3318125 / rank @@
+Normal rank
@@ Property / cites work @@
+On feedback vertex sets and nonseparating independent sets in cubic graphs
+Normal rank
@@ Property / cites work @@
+On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
+Normal rank
@@ Property / cites work @@
+On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
+Normal rank