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

@@ aliases / en / 0 / aliases / en / 0 @@
+Unit Interval Editing is Fixed-Parameter Tractable
@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 6498652
@@ Property / title @@
+Unit Interval Editing is Fixed-Parameter Tractable (English)
+Normal rank
@@ Property / zbMATH Open document ID @@
+.68135
@@ Property / zbMATH Open document ID: 1440.68135 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/978-3-662-47672-7_25
@@ Property / DOI: 10.1007/978-3-662-47672-7_25 / rank @@
+Normal rank
@@ Property / published in @@
+Automata, Languages, and Programming
@@ Property / published in: Automata, Languages, and Programming / rank @@
+Normal rank
@@ Property / publication date @@
+October 2015Timestamp +2015-10-27T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2015-10-27T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 27 October 2015 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+R10
@@ Property / Mathematics Subject Classification ID: 68R10 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C62
@@ Property / Mathematics Subject Classification ID: 05C62 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q27
@@ Property / Mathematics Subject Classification ID: 68Q27 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W40
@@ Property / Mathematics Subject Classification ID: 68W40 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6695584
@@ Property / zbMATH DE Number: 6695584 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6498652
@@ Property / zbMATH DE Number: 6498652 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+graph modification problem
@@ Property / zbMATH Keywords: graph modification problem / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+forbidden induced subgraph
@@ Property / zbMATH Keywords: forbidden induced subgraph / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+proper Helly circular-arc graph
@@ Property / zbMATH Keywords: proper Helly circular-arc graph / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+(proper, unit) interval model
@@ Property / zbMATH Keywords: (proper, unit) interval model / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+(proper, Helly) arc model
@@ Property / zbMATH Keywords: (proper, Helly) arc model / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+certifying algorithm
@@ Property / zbMATH Keywords: certifying algorithm / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+\(\{\text{claw},S_3,\overline{S_3},C_4\}\)-free graph
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W3022542130
@@ Property / OpenAlex ID: W3022542130 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1867877755
@@ Property / OpenAlex ID: W1867877755 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04470
@@ Property / arXiv ID: 1504.04470 / rank @@
+Normal rank
@@ Property / cites work @@
+Measuring Indifference: Unit Interval Vertex Deletion
+Normal rank
@@ Property / cites work @@
+NP-completeness results for edge modification problems
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability of graph modification problems for hereditary properties
+Normal rank
@@ Property / cites work @@
+Unit interval editing is fixed-parameter tractable
+Normal rank
@@ Property / cites work @@
+Chordal Editing is Fixed-Parameter Tractable
@@ Property / cites work: Chordal Editing is Fixed-Parameter Tractable / rank @@
+Normal rank
@@ Property / cites work @@
+A Polynomial Kernel for Proper Interval Vertex Deletion
+Normal rank
@@ Property / cites work @@
+Proper interval vertex deletion
@@ Property / cites work: Proper interval vertex deletion / rank @@
+Normal rank
@@ Property / cites work @@
+Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
+Normal rank
@@ Property / cites work @@
+The node-deletion problem for hereditary properties is NP-complete
+Normal rank
@@ Property / cites work @@
+Normal Helly circular-arc graphs and its subclasses
+Normal rank
@@ Property / cites work @@
+Edge deletion problems: branching facilitated by modular decomposition
+Normal rank
@@ Property / cites work @@
+Chordal deletion is fixed-parameter tractable
@@ Property / cites work: Chordal deletion is fixed-parameter tractable / rank @@
+Normal rank
@@ Property / cites work @@
+Q5588432
@@ Property / cites work: Q5588432 / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the Minimum Fill-In is NP-Complete
@@ Property / cites work: Computing the Minimum Fill-In is NP-Complete / rank @@
+Normal rank
@@ Property / cites work @@
+On chordal proper circular arc graphs
@@ Property / cites work: On chordal proper circular arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial kernels for proper interval completion and related problems
+Normal rank
@@ Property / cites work @@
+A Subexponential Parameterized Algorithm for Proper Interval Completion
+Normal rank
@@ Property / cites work @@
+On intervalizing \(k\)-colored graphs for DNA physical mapping
+Normal rank
@@ Property / cites work @@
+Linear Recognition of Almost Interval Graphs
@@ Property / cites work: Linear Recognition of Almost Interval Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
+Normal rank
@@ Property / cites work @@
+Chordal editing is fixed-parameter tractable
@@ Property / cites work: Chordal editing is fixed-parameter tractable / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
+Normal rank
@@ Property / cites work @@
+Fundamentals of parameterized complexity
@@ Property / cites work: Fundamentals of parameterized complexity / 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 @@
+Algorithms on circular-arc graphs
@@ Property / cites work: Algorithms on circular-arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Unit interval vertex deletion: fewer vertices are relevant
+Normal rank
@@ Property / cites work @@
+Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
+Normal rank
@@ Property / cites work @@
+Finding small separators in linear time via treewidth reduction
+Normal rank
@@ Property / cites work @@
+Structure theorems for some circular-arc graphs
@@ Property / cites work: Structure theorems for some circular-arc graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Proper Interval Vertex Deletion
@@ Property / cites work: Proper Interval Vertex Deletion / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:515577

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