Unit interval vertex deletion: fewer vertices are relevant
type: Item
instance of: scholarly article
title: Unit interval vertex deletion: fewer vertices are relevant
zbMATH Open document ID: 1391.68058
author: Yuping Ke
author: Yixin Cao
author: Xiating Ouyang
author: Wen-Jun Li
author: Jianxin Wang
published in: Journal of Computer and System Sciences
publication date: 2018-05-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/1607.01162
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6866854
zbMATH Keywords: unit interval graph
zbMATH Keywords: kernelization
zbMATH Keywords: graph modification problem
zbMATH Keywords: forbidden induced subgraph
zbMATH Keywords: (proper, unit) interval model
zbMATH Keywords: modulator
MaRDI profile type: Publication
OpenAlex ID: W2964327184
arXiv ID: 1607.01162
cites work: Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
cites work: Measuring Indifference: Unit Interval Vertex Deletion
cites work: A short proof that `proper = unit'
cites work: Unit interval editing is fixed-parameter tractable
cites work: Chordal editing is fixed-parameter tractable
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: On rigid circuit graphs
cites work: A polynomial kernel for trivially perfect editing
cites work: Intersection Theorems for Systems of Sets
cites work: Parametrized complexity theory.
cites work: A Polynomial Kernel for Proper Interval Vertex Deletion
cites work: Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
cites work: Proper interval vertex deletion
cites work: $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Optimal greedy algorithms for indifference graphs
cites work: Chordal deletion is fixed-parameter tractable
cites work: Q5588432
Wikidata QID: Q130160419
DOI: 10.1016/J.JCSS.2018.01.001
description: scientific article