Feedback vertex set in hypercubes

DOI10.1016/S0020-0190(00)00127-7MaRDI QIDQ294845zbMATH OpenWikidataFDO

Authors 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

zbMATH Keywords

hypercubecodescyclecombinatorial problemsfeedback vertex set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Feedback vertex sets in mesh-based networks
• Minimum feedback vertex sets in shuffle-based interconnection networks
• Structural Information and Communication Complexity
• Feedback numbers of augmented cubes \({AQ}_n*\)
• Feedback vertex sets in star graphs

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3397423 (Why is no real title available?)
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Almost exact minimum feedback vertex set in meshes and butterflies
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Approximation algorithms for combinatorial problems
• Feedback vertex sets and cyclically reducible graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• On locating minimum feedback vertex sets
• On the feedback vertex set problem in permutation graphs
• Size bounds for dynamic monopolies

Cited in

(33)

• The feedback number of crossed cube networks
• The decycling number of \(P_m\square P^\ast_n\)
• Feedback vertex sets in mesh-based networks
• Induced forests in some distance-regular graphs
• Decycling bubble sort graphs
• Structural Information and Communication Complexity
• Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs
• Minimum feedback vertex set and acyclic coloring.
• New bounds on the decycling number of generalized de Bruijn digraphs
• New formulae for the decycling number of graphs
• Maximum induced forests of product graphs
• Feedback numbers of augmented cubes \({AQ}_n*\)
• A new formula for the decycling number of regular graphs
• An efficient algorithm for minimum feedback vertex sets in rotator graphs
• Minimum feedback vertex sets in shuffle-based interconnection networks
• Feedback vertex sets in cubic multigraphs
• Feedback numbers of de Bruijn digraphs
• Feedback vertex number of Sierpiński-type graphs
• Dynamic monopolies and feedback vertex sets in hexagonal grids
• Decycling bipartite graphs
• Minimum feedback arc sets in rotator and incomplete rotator graphs
• Feedback vertex sets on restricted bipartite graphs
• The size of graphs with given feedback vertex number
• Feedback numbers of Kautz digraphs
• New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
• Two Hardness Results on Feedback Vertex Sets
• New upper bounds on feedback vertex numbers in butterflies
• Feedback vertex sets in star graphs
• A feedback vertex set of 2-degenerate graphs
• Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
• 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

This page was built for publication: Feedback vertex set in hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q294845)