Boundary classes for graph problems involving non-local properties
From MaRDI portal
Publication:2401761
DOI10.1016/j.tcs.2017.06.012zbMath1372.68142OpenAlexW2731362769MaRDI QIDQ2401761
Publication date: 5 September 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.06.012
Analysis of algorithms and problem complexity (68Q25) 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45)
Related Items (8)
CPG graphs: some structural and hardness results ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Non-empty intersection of longest paths in \(H\)-free graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Intersection graphs of non-crossing paths ⋮ 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 ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Cites Work
- A complexity dichotomy and a new boundary class for the dominating set problem
- The VC-dimension of graphs with respect to \(k\)-connected subgraphs
- \textsc{max-cut} and containment relations in graphs
- Critical hereditary graph classes: a survey
- Boundary properties of graphs for algorithmic graph problems
- Exact exponential algorithms.
- Recent developments on graphs of bounded clique-width
- Vertex and edge covers with clustering properties: Complexity and algorithms
- An augmenting path algorithm for linear matroid parity
- Matching theory
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- On maximal independent sets of vertices in claw-free graphs
- Matroid matching and some applications
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- NP-completeness and degree restricted spanning trees
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- The complexity of generalized clique covering
- A partial k-arboretum of graphs with bounded treewidth
- A characterization of Tutte invariants of 2-polymatroids
- The VC-dimension of set systems defined by graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On limited nondeterminism and the complexity of the V-C dimension
- Boundary classes of graphs for the dominating set problem
- A new bound on the feedback vertex sets in cubic graphs
- HAMILTONian circuits in chordal bipartite graphs
- Feedback vertex set on graphs of low clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- On the maximum independent set problem in subclasses of subcubic graphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
- Handle-rewriting hypergraph grammars
- On line graphs of subcubic triangle-free graphs
- NP-hard graph problems and boundary classes of graphs
- Approximating clique-width and branch-width
- Feedback vertex sets in cubic multigraphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A Dichotomy for Upper Domination in Monogenic Classes
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Easy problems for tree-decomposable graphs
- A Fast, Simpler Algorithm for the Matroid Parity Problem
- On Hadwiger's Number and the Stability Number
- Graph minors. II. Algorithmic aspects of tree-width
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Independence and Efficient Domination on P6-free Graphs
- A weighted linear matroid parity algorithm
- Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
- Independent Set in P5-Free Graphs in Polynomial Time
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Boundary classes for graph problems involving non-local properties
