Contracting graphs to paths and trees (Q2441588): Difference between revisions

← Older edit

@@ aliases / en / 0 / aliases / en / 0 @@
+Contracting Graphs to Paths and Trees
@@ description / en / description / en @@
+scientific article; zbMATH DE number 6046496
@@ Property / title @@
+Contracting Graphs to Paths and Trees (English)
@@ Property / title: Contracting Graphs to Paths and Trees (English) / rank @@
+Normal rank
@@ Property / zbMATH Open document ID @@
+.68228
@@ Property / zbMATH Open document ID: 1310.68228 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/978-3-642-28050-4_5
@@ Property / DOI: 10.1007/978-3-642-28050-4_5 / rank @@
+Normal rank
@@ Property / published in @@
+Parameterized and Exact Computation
@@ Property / published in: Parameterized and Exact Computation / rank @@
+Normal rank
@@ Property / publication date @@
+June 2012Timestamp +2012-06-15T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2012-06-15T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 15 June 2012 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6046496
@@ Property / zbMATH DE Number: 6046496 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2111720465
@@ Property / OpenAlex ID: W2111720465 / rank @@
+Normal rank
@@ Property / cites work @@
+Color-coding
@@ Property / cites work: Color-coding / rank @@
+Normal rank
@@ Property / cites work @@
+Edge-contraction problems
@@ Property / cites work: Edge-contraction problems / rank @@
+Normal rank
@@ Property / cites work @@
+Measuring Indifference: Unit Interval Vertex Deletion
+Normal rank
@@ Property / cites work @@
+Enumerate and Measure: Improving Parameter Budget Management
+Normal rank
@@ Property / cites work @@
+ON DISJOINT CYCLES
@@ Property / cites work: ON DISJOINT CYCLES / rank @@
+Normal rank
@@ Property / cites work @@
+(Meta) Kernelization
@@ Property / cites work: (Meta) Kernelization / rank @@
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+Kernel bounds for disjoint cycles and disjoint paths
+Normal rank
@@ Property / cites work @@
+Contractibility and NP-completeness
@@ Property / cites work: Contractibility and NP-completeness / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability of graph modification problems for hereditary properties
+Normal rank
@@ Property / cites work @@
+On Feedback Vertex Set New Measure and New Structures
+Normal rank
@@ Property / cites work @@
+Improved algorithms for feedback vertex set problems
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
+Normal rank
@@ Property / cites work @@
+An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
+Normal rank
@@ Property / cites work @@
+Incompressibility through Colors and IDs
@@ Property / cites work: Incompressibility through Colors and IDs / rank @@
+Normal rank
@@ Property / cites work @@
+Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
+Normal rank
@@ Property / cites work @@
+Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
+Normal rank
@@ Property / cites work @@
+Contracting graphs to paths and trees
@@ Property / cites work: Contracting graphs to paths and trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q5417631
@@ Property / cites work: Q5417631 / rank @@
+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 @@
+Obtaining a Planar Graph by Vertex Deletion
@@ Property / cites work: Obtaining a Planar Graph by Vertex Deletion / rank @@
+Normal rank
@@ Property / cites work @@
+Q4231923
@@ Property / cites work: Q4231923 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity classification of some edge modification problems
+Normal rank
@@ Property / cites work @@
+A Quartic Kernel for Pathwidth-One Vertex Deletion
+Normal rank
@@ Property / cites work @@
+A 4             <i>k</i>             <sup>2</sup>             kernel for feedback vertex set
+Normal rank
@@ Property / cites work @@
+Proper Interval Vertex Deletion
@@ Property / cites work: Proper Interval Vertex Deletion / rank @@
+Normal rank
@@ Property / cites work @@
+On the removal of forbidden graphs by edge-deletion or by edge- contraction
+Normal rank
@@ Property / cites work @@
+On the NP-hardness of edge-deletion and -contraction problems
+Normal rank
@@ Property / cites work @@
+Node-and edge-deletion NP-complete problems
@@ Property / cites work: Node-and edge-deletion NP-complete problems / rank @@
+Normal rank
@@ Property / cites work @@
+The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
+Normal rank
@@ Property / cites work @@
+Edge-Deletion Problems
@@ Property / cites work: Edge-Deletion Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
+Normal rank
@@ Property / cites work @@
+Deterministic Parameterized Connected Vertex Cover
+Normal rank
@@ Property / cites work @@
+Fast FPT-Algorithms for Cleaning Grids
@@ Property / cites work: Fast FPT-Algorithms for Cleaning Grids / rank @@
+Normal rank
@@ Property / cites work @@
+Parametrized complexity theory.
@@ Property / cites work: Parametrized complexity theory. / rank @@
+Normal rank
@@ Property / cites work @@
+Infeasibility of instance compression and succinct PCPs for NP
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Increasing the Minimum Degree of a Graph by Contractions
+Normal rank
@@ Property / cites work @@
+Contracting chordal graphs and bipartite graphs to paths and trees
+Normal rank
@@ Property / cites work @@
+Q2911626
@@ Property / cites work: Q2911626 / rank @@
+Normal rank
@@ Property / cites work @@
+Obtaining a planar graph by vertex deletion
@@ Property / cites work: Obtaining a planar graph by vertex deletion / rank @@
+Normal rank
@@ Property / cites work @@
+Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
+Normal rank
@@ Property / cites work @@
+Proper interval vertex deletion
@@ Property / cites work: Proper interval vertex deletion / rank @@
+Normal rank