Feedback vertex set in hypercubes
From MaRDI portal
Publication:294845
DOI10.1016/S0020-0190(00)00127-7zbMath1338.68218WikidataQ57832155 ScholiaQ57832155MaRDI QIDQ294845
Riccardo Focardi, Flaminia L. Luccio, David Peleg
Publication date: 16 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000001277?np=y
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The size of graphs with given feedback vertex number, New formulae for the decycling number of graphs, A feedback vertex set of 2-degenerate graphs, Feedback vertex sets in mesh-based networks, New upper bounds on feedback vertex numbers in butterflies, The decycling number of $P_{m} \square P_{n}^{\ast}$, A new formula for the decycling number of regular graphs, Decycling bipartite graphs, Feedback numbers of Kautz digraphs, Feedback vertex sets on restricted bipartite graphs, New bounds on the decycling number of generalized de Bruijn digraphs, Maximum induced forests of product graphs, Induced forests in some distance-regular graphs, Dynamic monopolies and feedback vertex sets in hexagonal grids, Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs, On the bounds of feedback numbers of \((n,k)\)-star graphs, On the decycling number of generalized Kautz digraphs, The decycling number of generalized Petersen graphs, Decycling bubble sort graphs, Two Hardness Results on Feedback Vertex Sets, MINIMUM FEEDBACK ARC SETS IN ROTATOR AND INCOMPLETE ROTATOR GRAPHS, Feedback numbers of de Bruijn digraphs, An efficient algorithm for minimum feedback vertex sets in rotator graphs, Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis, Minimum feedback vertex sets in shuffle-based interconnection networks, Feedback vertex sets in star graphs, New bounds on the size of the minimum feedback vertex set in meshes and butterflies., Minimum feedback vertex set and acyclic coloring., Feedback vertex number of Sierpiński-type graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- On locating minimum feedback vertex sets
- Almost exact minimum feedback vertex set in meshes and butterflies
- Approximation algorithms for combinatorial problems
- Size bounds for dynamic monopolies
- On the feedback vertex set problem in permutation graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Feedback vertex sets and cyclically reducible graphs
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
