Detecting fixed patterns in chordal graphs in polynomial time

DOI10.1007/s00453-013-9748-5zbMath1291.68173MaRDI QIDQ2249737

Pim van 't Hof, Daniël Paulusma, Pinar Heggernes, Rémy Belmonte, Marcin Kaminski, Petr A. Golovach

Publication date: 3 July 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/10684/1/10684.pdf

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C83: Graph minors

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Induced Disjoint Paths in Claw-Free Graphs, Contracting bipartite graphs to paths and cycles, Contracting bipartite graphs to paths and cycles, Unnamed Item, Few induced disjoint paths for \(H\)-free graphs, The complexity of contracting bipartite graphs into small cycles, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Cops and robber on oriented graphs with respect to push operation, Graph editing to a fixed target, Detecting induced minors in AT-free graphs, Induced disjoint paths in AT-free graphs, Parameterized complexity of set-restricted disjoint paths on chordal graphs, Few induced disjoint paths for \(H\)-free graphs, Mim-width. I. Induced path problems, On strictly chordality-\(k\) graphs, The (theta, wheel)-free graphs. IV: Induced paths and cycles, Induced disjoint paths in circular-arc graphs in linear time

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graph contractions and induced minors
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Containment relations in split graphs
• On rigid circuit graphs
• Partitioning graphs into connected parts
• On the complexity of testing for odd holes and induced odd paths
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations
• The complexity of induced minors and related problems
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• The \(k\)-in-a-path problem for claw-free graphs
• Parametrized complexity theory.
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Edge Contractions in Subclasses of Chordal Graphs
• Contracting a Chordal Graph to a Split Graph or a Tree
• Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• Contractibility and NP-completeness
• Graph Classes: A Survey
• Finding topological subgraphs is fixed-parameter tractable
• Detecting induced subgraphs