Interval Deletion Is Fixed-Parameter Tractable
Copyright policy )Interval Deletion Is Fixed-Parameter Tractable
We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10 k ⋅ n O (1) for this problem—that is, we show that the problem is fixed-parameter tractable.
- Hong Kong Polytechnic University China (People's Republic of)
- Hungarian Academy of Sciences Hungary
- Library and Information Centre of the Hungarian Academy of Sciences Hungary
- Magyar Tudományos Akadémia Könyvtára (Library of the Hungarian Academy of Sciences) Hungary
- MTA Institute for Computer Science and Control Hungary
FOS: Computer and information sciences, QA75 Electronic computers. Computer science / számítástechnika, Discrete Mathematics (cs.DM), számítógéptudomány, G.2.2, G.2.2; F.2.2, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), QA74 Analysis / analízis, F.2.2, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, QA75 Electronic computers. Computer science / számítástechnika, Discrete Mathematics (cs.DM), számítógéptudomány, G.2.2, G.2.2; F.2.2, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), QA74 Analysis / analízis, F.2.2, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).35 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!