Boundary classes for graph problems involving non-local properties
From MaRDI portal
Publication:2401761
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
Cites work
- [/wiki/Item:Q3115709 scientific article; zbMATH DE number 6004968 (Why is no real title available?)]
- [/wiki/Item:Q3318125 scientific article; zbMATH DE number 3848625 (Why is no real title available?)]
- [/wiki/Item:Q3888545 scientific article; zbMATH DE number 3694608 (Why is no real title available?)]
- [/wiki/Item:Q4198056 scientific article; zbMATH DE number 3639144 (Why is no real title available?)]
- [/wiki/Item:Q4448764 scientific article; zbMATH DE number 2044943 (Why is no real title available?)]
- [/wiki/Item:Q5315023 scientific article; zbMATH DE number 2203240 (Why is no real title available?)]
- A Fast, Simpler Algorithm for the Matroid Parity Problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- 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 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
- Independence and efficient domination on \(P_6\)-free graphs
- Independent set in \(P_5\)-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 Hadwiger's Number and the Stability Number
- 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 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 Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- 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
- Recent developments on graphs of bounded clique-width
- 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
- The complexity of generalized clique covering
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Upper bounds to the clique width of graphs
- Vertex and edge covers with clustering properties: Complexity and algorithms
- \textsc{max-cut} and containment relations in graphs
Cited in
(12)- scientific article; zbMATH DE number 6004968 (Why is no real title available?)
- Boundary properties of graphs for algorithmic graph problems
- CPG graphs: some structural and hardness results
- Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs
- Intersection graphs of non-crossing paths
- Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
- 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
- Connected vertex cover for \((sP_1+P_5)\)-free graphs
- On cycle transversals and their connected variants in the absence of a small linear forest
- Independent feedback vertex set for \(P_5\)-free graphs
- Non-empty intersection of longest paths in \(H\)-free graphs
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)
