Detecting fixed patterns in chordal graphs in polynomial time
DOI10.1007/S00453-013-9748-5zbMATH Open1291.68173OpenAlexW2003458989MaRDI QIDQ2249737FDOQ2249737
Authors: Rémy Belmonte, Pinar Heggernes, Pim Van 't Hof, Daniël Paulusma, Petr A. Golovach, Marcin Kamiński 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithmic graph theory and perfect graphs
- Graph minors. XIII: The disjoint paths problem
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Treewidth. Computations and approximations
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Partitioning graphs into connected parts
- Title not available (Why is that?)
- Finding topological subgraphs is fixed-parameter tractable
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- The complexity of induced minors and related problems
- On graph contractions and induced minors
- Edge contractions in subclasses of chordal graphs
- Finding contractions and induced minors in chordal graphs via disjoint paths
- 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
- Contraction checking in graphs on surfaces
- A note on contracting claw-free graphs
- Contracting a chordal graph to a split graph or a tree
- Containment relations in split graphs
- On the complexity of testing for odd holes and induced odd paths
- The \(k\)-in-a-path problem for claw-free graphs
Cited In (24)
- Few induced disjoint paths for \(H\)-free graphs
- Few induced disjoint paths for \(H\)-free graphs
- Finding contractions and induced minors in chordal graphs via disjoint paths
- A note on contracting claw-free graphs
- Containment relations in split graphs
- On strictly chordality-\(k\) graphs
- The complexity of contracting bipartite graphs into small cycles
- Contracting a chordal graph to a split graph or a tree
- Contracting bipartite graphs to paths and cycles
- Induced disjoint paths in claw-free graphs
- Graph editing to a fixed target
- Mim-width. I. Induced path problems
- Detecting induced minors in AT-free graphs
- On graph contractions and induced minors
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- Contracting bipartite graphs to paths and cycles
- Title not available (Why is that?)
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths and connected subgraphs for \(H\)-free graphs
- Induced disjoint paths in circular-arc graphs in linear time
- A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns
- Edge contractions in subclasses of chordal graphs
- Parameterized complexity of set-restricted disjoint paths on chordal graphs
- Cops and robber on oriented graphs with respect to push operation
Uses Software
This page was built for publication: Detecting fixed patterns in chordal graphs in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249737)
