On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
From MaRDI portal
Publication:1123898
DOI10.1016/0012-365X(88)90226-9zbMath0678.05026OpenAlexW2069169607WikidataQ59442098 ScholiaQ59442098MaRDI QIDQ1123898
Shuichi Ueno, Yoji Kajitani, Shin'ya Gotoh
Publication date: 1988
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(88)90226-9
matching problemnonseparating independent setfeedback set problem3-regular graphsminimum feedback setNP-complete graph problemsspanning set problem
Related Items
Some observations on holographic algorithms, A parameterized complexity view on collapsing \(k\)-cores, The size of graphs with given feedback vertex number, On bipartization of cubic graphs by removal of an independent set, A feedback vertex set of 2-degenerate graphs, On line graphs of subcubic triangle-free graphs, Boundary classes for graph problems involving non-local properties, Decycling bipartite graphs, Maximum genus and maximum nonseparating independent set of a 3-regular graph, A \(9k\) kernel for nonseparating independent set in planar graphs, Corrigendum to ``Cycle transversals in perfect graphs and cographs, Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity, Feedback vertex set on Hamiltonian graphs, A bound on the dissociation number, Feedback vertex set reconfiguration in planar graphs, Splitting plane graphs to outerplanarity, Domination number and feedback vertex number of complements of line graphs, Complexity analysis of \(P_3\)-convexity problems on bounded-degree and planar graphs, The connected vertex cover problem in \(k\)-regular graphs, Complexity and Approximation Results for the Connected Vertex Cover Problem, Constraint bipartite vertex cover: simpler exact algorithms and implementations, Unnamed Item, The cyclomatic number of a graph and its independence polynomial at \(- 1\), A naive algorithm for feedback vertex set, Complexity and algorithms for the connected vertex cover problem in 4-regular graphs, On finding orientations with the fewest number of vertices with small out-degree, On feedback vertex set: new measure and new structures, Dominating and large induced trees in regular graphs, Acyclic polynomials of graphs, Approximability of the independent feedback vertex set problem for bipartite graphs, A simple proof of an inequality connecting the alternating number of independent sets and the decycling number, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization, Connected vertex cover for \((sP_1+P_5)\)-free graphs, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, On cycle transversals and their connected variants in the absence of a small linear forest, Feedback arc number and feedback vertex number of Cartesian product of directed cycles, Nonseparating independent sets of Cartesian product graphs, (In)approximability of maximum minimal FVS, On the maximum induced forests of a connected cubic graph without triangles, Minimum weakly fundamental cycle bases are hard to find, Vertex and edge covers with clustering properties: Complexity and algorithms, Unnamed Item, Extension and its price for the connected vertex cover problem, Revisiting connected vertex cover: FPT algorithms and lossy kernels, On reconfigurability of target sets
Cites Work
