scientific article; zbMATH DE number 219267
From MaRDI portal
Publication:4694754
zbMath0768.68181MaRDI QIDQ4694754
Publication date: 29 June 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
digraphapproximation algorithmrandom walktournamentfeedback vertex setacyclic digraphChurch-Rosser propertyMarkovian algorithmplynomial timerandomly generated digraphsRosen's fvs-algorithm
Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)
Related Items (21)
Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ Parameterized complexity of \(d\)-hitting set with quotas ⋮ On enumerating all minimal solutions of feedback problems ⋮ Feedback arc set in bipartite tournaments is NP-complete ⋮ Polynomial time algorithms for tracking path problems ⋮ Component order connectivity in directed graphs ⋮ Packing arc-disjoint cycles in tournaments ⋮ Improved bounds for minimal feedback vertex sets in tournaments ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Safe sets and in-dominating sets in digraphs ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Quasi-hamiltonian paths in semicomplete multipartite digraphs ⋮ Kernels for feedback arc set in tournaments ⋮ Open problems around exact algorithms ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ Linear programming based approximation algorithms for feedback set problems in bipartite tournaments ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms ⋮ Tournaments and Semicomplete Digraphs
This page was built for publication:
