Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs (Q5915760): Difference between revisions

Revision as of 21:43, 18 July 2024

scientific article; zbMATH DE number 7040836

Language	Label	Description	Also known as
English	Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs	scientific article; zbMATH DE number 7040836

Statements

instance of

scholarly article

0 references

title

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

0 references

zbMATH Open document ID

1495.68182

0 references

1407.05225

0 references

DOI

10.1007/978-3-662-55751-8_30

0 references

10.1016/j.dam.2018.11.017

0 references

0 references

0 references

Fundamentals of Computation Theory

0 references

Discrete Applied Mathematics

0 references

publication date

22 November 2017

0 references

22 March 2019

0 references

full work available at URL

https://arxiv.org/abs/1701.04634

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

MaRDI publication profile

0 references

0 references

0 references

0 references

subset feedback vertex set

0 references

graph algorithms

0 references

interval graphs

0 references

permutation graphs

0 references

cites work

Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference

0 references

Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem

0 references

Graph classes with structured neighborhoods and algorithmic applications

0 references

Q4281625

0 references

Q3694712

0 references

On domination problems for permutation and other graphs

0 references

Graph Classes: A Survey

0 references

Feedback vertex set on graphs of low clique-width

0 references

Faster exact algorithms for some terminal set problems

0 references

The complexity of generalized clique covering

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Subset Feedback Vertex Set Is Fixed-Parameter Tractable

0 references

An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem

0 references

Exact Algorithms via Monotone Local Search

0 references

Enumerating minimal subset feedback vertex sets

0 references

Incidence matrices and interval graphs

0 references

Multiway cuts in node weighted graphs

0 references

Subset feedback vertex sets in chordal graphs

0 references

Algorithmic graph theory and perfect graphs

0 references

ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

0 references

Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs

0 references

Feedback vertex set on AT-free graphs

0 references

On the feedback vertex set problem in permutation graphs

0 references

Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs

0 references

A linear-time algorithm for the weighted feedback vertex problem on interval graphs

0 references

Weighted domination of cocomparability graphs

0 references

Modular decomposition and transitive orientation

0 references

Restricted vertex multicut on permutation graphs

0 references

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

0 references

Efficient graph representations

0 references

Node-Deletion Problems on Bipartite Graphs

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5915760

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