Feedback vertex sets and cyclically reducible graphs
From MaRDI portal
Publication:3771642
DOI10.1145/3149.3159zbMath0633.68064OpenAlexW2047766986MaRDI QIDQ3771642
Ching-Chy Wang, Errol L. Lloyd, Mary Lou Soffa
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3149.3159
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Theory of operating systems (68N25)
Related Items
The size of graphs with given feedback vertex number ⋮ Feedback vertex set in hypercubes ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ On enumerating all minimal solutions of feedback problems ⋮ Feedback arc set in bipartite tournaments is NP-complete ⋮ Feedback vertex sets in mesh-based networks ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Parallelism and the feedback vertex set problem ⋮ On locating minimum feedback vertex sets ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ Feedback numbers of Kautz digraphs ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ New bounds on the decycling number of generalized de Bruijn digraphs ⋮ The decycling number of outerplanar graphs ⋮ On the decycling number of generalized Kautz digraphs ⋮ Solving the feedback vertex set problem on undirected graphs ⋮ New formulae for the bipartite vertex frustration and decycling number of graphs ⋮ A constraint programming approach to cutset problems ⋮ Feedback numbers of de Bruijn digraphs ⋮ Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem ⋮ 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 arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Feedback vertex sets in star graphs ⋮ New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
