Publication:4694754
From MaRDI portal
zbMath0768.68181MaRDI QIDQ4694754
Publication date: 29 June 1993
digraph; approximation algorithm; random walk; tournament; feedback vertex set; acyclic digraph; Church-Rosser property; Markovian algorithm; plynomial time; randomly generated digraphs; Rosen's fvs-algorithm
68Q25: Analysis of algorithms and problem complexity
60G50: Sums of independent random variables; random walks
68R10: Graph theory (including graph drawing) in computer science
05C20: Directed graphs (digraphs), tournaments
Related Items
Improved bounds for minimal feedback vertex sets in tournaments, A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Linear programming based approximation algorithms for feedback set problems in bipartite tournaments, Kernels for feedback arc set in tournaments, Parameterized algorithms for feedback set problems and their duals in tournaments, Parameterized complexity of \(d\)-hitting set with quotas, Feedback arc set in bipartite tournaments is NP-complete, On enumerating all minimal solutions of feedback problems, Polynomial kernels for deletion to classes of acyclic digraphs, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Polynomial time algorithms for tracking path problems, Component order connectivity in directed graphs, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Fixed-parameter tractability results for feedback set problems in tournaments, Open problems around exact algorithms, Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms, Packing arc-disjoint cycles in tournaments, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, Tournaments and Semicomplete Digraphs
