Boundary classes for graph problems involving non-local properties
From MaRDI portal
Eulerian and Hamiltonian graphs (05C45) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
Cites work
- \textsc{max-cut} and containment relations in graphs
- A characterization of Tutte invariants of 2-polymatroids
- A complexity dichotomy and a new boundary class for the dominating set problem
- A dichotomy for upper domination in monogenic classes
- A Fast, Simpler Algorithm for the Matroid Parity Problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A new bound on the feedback vertex sets in cubic graphs
- A partial k-arboretum of graphs with bounded treewidth
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- A weighted linear matroid parity algorithm
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- An augmenting path algorithm for linear matroid parity
- Approximating clique-width and branch-width
- Boundary classes of graphs for the dominating set problem
- Boundary properties of graphs for algorithmic graph problems
- Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Continuous sets of the boundary classes of graphs for coloring problems
- Critical hereditary graph classes: a survey
- Easy problems for tree-decomposable graphs
- Exact exponential algorithms.
- Feedback vertex set on graphs of low clique-width
- Feedback vertex sets in cubic multigraphs
- Graph minors. II. Algorithmic aspects of tree-width
- HAMILTONian circuits in chordal bipartite graphs
- Handle-rewriting hypergraph grammars
- scientific article; zbMATH DE number 6004968 (Why is no real title available?)
- scientific article; zbMATH DE number 3848625 (Why is no real title available?)
- scientific article; zbMATH DE number 3694608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Independence and efficient domination on \(P_6\)-free graphs
- Independent set in P₅-free graphs in polynomial time
- Linear time solvable optimization problems on graphs of bounded clique-width
- Matching theory
- Matroid matching and some applications
- NP-completeness and degree restricted spanning trees
- NP-hard graph problems and boundary classes of graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- On Hadwiger's Number and the Stability Number
- On limited nondeterminism and the complexity of the V-C dimension
- On line graphs of subcubic triangle-free graphs
- On maximal independent sets of vertices in claw-free graphs
- On the maximum independent set problem in subclasses of subcubic graphs
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Recent developments on graphs of bounded clique-width
- The complexity of generalized clique covering
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The Rectilinear Steiner Tree Problem is NP-Complete
- The VC-dimension of graphs with respect to k-connected subgraphs
- The VC-dimension of set systems defined by graphs
- Upper bounds to the clique width of graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
Cited in
(14)- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- Independent feedback vertex set for P₅-free graphs
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- NP-hard graph problems and boundary classes of graphs
- Non-empty intersection of longest paths in H-free graphs
- scientific article; zbMATH DE number 6004968 (Why is no real title available?)
- Boundary properties of graphs for algorithmic graph problems
- On cycle transversals and their connected variants in the absence of a small linear forest
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- Intersection graphs of non-crossing paths
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- Connected vertex cover on AT-free graphs
- Complexity framework for forbidden subgraphs. I: The framework
- CPG graphs: some structural and hardness results
This page was built for publication: Boundary classes for graph problems involving non-local properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401761)
