Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
type: Item
instance of: scholarly article
title: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
zbMATH Open document ID: 1119.68134
author: Jiong Guo
author: Jens Gramm
author: Falk Hüffner
author: Rolf Niedermeier
author: Sebastian Wernicke
published in: Journal of Computer and System Sciences
publication date: 2006-12-07T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 5078611
zbMATH Keywords: fixed-parameter tractability
zbMATH Keywords: iterative compression
zbMATH Keywords: graph algorithm
zbMATH Keywords: graph modification problem
zbMATH Keywords: feedback set problem
MaRDI profile type: Publication
full work available at URL: j.jcss.2006.02.001
OpenAlex ID: W2157295389
Wikidata QID: Q56209811
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Algorithm Theory - SWAT 2004
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Q4488089
cites work: ON DISJOINT CYCLES
cites work: Introduction to algorithms
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Computing and Combinatorics
cites work: Fixed-parameter tractability results for feedback set problems in tournaments
cites work: Q4027320
cites work: Q4393480
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Algorithms and Data Structures
cites work: Q4808679
cites work: Q3145802
cites work: Q3439692
cites work: Experimental and Efficient Algorithms
cites work: Parameterized and Exact Computation
cites work: On the power of unique 2-prover 1-round games
cites work: The approximation of maximum subgraph problems
cites work: Mathematical Foundations of Computer Science 2004
cites work: Q5710169
cites work: Optimization, approximation, and complexity classes
cites work: Parameterized algorithms for feedback set problems and their duals in tournaments
cites work: Q4425958
cites work: Q3439693
cites work: Finding odd cycle transversals.
cites work: On enumerating all minimal solutions of feedback problems
DOI: 10.1016/J.JCSS.2006.02.001
description: scientific article; zbMATH DE number 5078611