Unit interval editing is fixed-parameter tractable (Q515577): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(7 intermediate revisions by 6 users not shown)
aliases / en / 0aliases / en / 0
 
Unit Interval Editing is Fixed-Parameter Tractable
description / endescription / en
scientific article
scientific article; zbMATH DE number 6498652
Property / title
 
Unit Interval Editing is Fixed-Parameter Tractable (English)
Property / title: Unit Interval Editing is Fixed-Parameter Tractable (English) / rank
 
Normal rank
Property / zbMATH Open document ID
 
Property / zbMATH Open document ID: 1440.68135 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/978-3-662-47672-7_25 / rank
 
Normal rank
Property / published in
 
Property / published in: Automata, Languages, and Programming / rank
 
Normal rank
Property / publication date
 
27 October 2015
Timestamp+2015-10-27T00:00:00Z
Timezone+00:00
CalendarGregorian
Precision1 day
Before0
After0
Property / publication date: 27 October 2015 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 68Q27 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 68W40 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6498652 / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W3022542130 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1867877755 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1504.04470 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Measuring Indifference: Unit Interval Vertex Deletion / rank
 
Normal rank
Property / cites work
 
Property / cites work: NP-completeness results for edge modification problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fixed-parameter tractability of graph modification problems for hereditary properties / rank
 
Normal rank
Property / cites work
 
Property / cites work: Unit interval editing is fixed-parameter tractable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chordal Editing is Fixed-Parameter Tractable / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Polynomial Kernel for Proper Interval Vertex Deletion / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proper interval vertex deletion / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The node-deletion problem for hereditary properties is NP-complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: Normal Helly circular-arc graphs and its subclasses / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edge deletion problems: branching facilitated by modular decomposition / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chordal deletion is fixed-parameter tractable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5588432 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing the Minimum Fill-In is NP-Complete / rank
 
Normal rank
Property / cites work
 
Property / cites work: On chordal proper circular arc graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial kernels for proper interval completion and related problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Subexponential Parameterized Algorithm for Proper Interval Completion / rank
 
Normal rank
Property / cites work
 
Property / cites work: On intervalizing \(k\)-colored graphs for DNA physical mapping / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear Recognition of Almost Interval Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection / rank
 
Normal rank
Property / cites work
 
Property / cites work: Chordal editing is fixed-parameter tractable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fundamentals of parameterized complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Incidence matrices and interval graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithms on circular-arc graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Unit interval vertex deletion: fewer vertices are relevant / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding small separators in linear time via treewidth reduction / rank
 
Normal rank
Property / cites work
 
Property / cites work: Structure theorems for some circular-arc graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proper Interval Vertex Deletion / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 13:09, 13 July 2024

scientific article; zbMATH DE number 6498652
  • Unit Interval Editing is Fixed-Parameter Tractable
Language Label Description Also known as
English
Unit interval editing is fixed-parameter tractable
scientific article; zbMATH DE number 6498652
  • Unit Interval Editing is Fixed-Parameter Tractable

Statements

Unit interval editing is fixed-parameter tractable (English)
0 references
Unit Interval Editing is Fixed-Parameter Tractable (English)
0 references
0 references
16 March 2017
0 references
27 October 2015
0 references
graph modification problem
0 references
forbidden induced subgraph
0 references
proper Helly circular-arc graph
0 references
(proper, unit) interval model
0 references
(proper, Helly) arc model
0 references
certifying algorithm
0 references
\(\{\text{claw},S_3,\overline{S_3},C_4\}\)-free graph
0 references
0 references

Identifiers

0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references