Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs

DOI10.1007/978-3-662-55751-8_30zbMath1495.68182arXiv1701.04634OpenAlexW2574748442WikidataQ128744089 ScholiaQ128744089MaRDI QIDQ5915760

Spyridon Tzimas, Charis Papadopoulos

Publication date: 22 November 2017

Published in: Discrete Applied Mathematics, Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.04634

zbMATH Keywords

graph algorithmsinterval graphspermutation graphssubset feedback vertex set

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Signed and weighted graphs (05C22)

Related Items (13)

Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Classifying subset feedback vertex set for \(H\)-free graphs ⋮ Parameterized complexity of multicut in weighted trees ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Unnamed Item ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Mim-width. II. The feedback vertex set problem ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Restricted vertex multicut on permutation graphs
• Enumerating minimal subset feedback vertex sets
• Feedback vertex set on AT-free graphs
• On domination problems for permutation and other graphs
• The complexity of generalized clique covering
• Modular decomposition and transitive orientation
• On the feedback vertex set problem in permutation graphs
• Weighted domination of cocomparability graphs
• Efficient graph representations
• Algorithmic graph theory and perfect graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Feedback vertex set on graphs of low clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Faster exact algorithms for some terminal set problems
• Incidence matrices and interval graphs
• Subset feedback vertex sets in chordal graphs
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Node-Deletion Problems on Bipartite Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Graph Classes: A Survey
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Multiway cuts in node weighted graphs
• Exact Algorithms via Monotone Local Search
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs

This page was built for publication: Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs