Detecting induced minors in AT-free graphs

DOI10.1016/J.TCS.2013.02.029zbMATH Open1296.05183OpenAlexW1990607348MaRDI QIDQ390909FDOQ390909

Petr A. Golovach, Dieter Kratsch, Daniël Paulusma

Publication date: 9 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.02.029

Recommendations

• Detecting induced minors in AT-free graphs
• On graph contractions and induced minors
• Detecting induced star-like minors in polynomial time
• Detecting fixed patterns in chordal graphs in polynomial time
• Induced disjoint paths in AT-free graphs

zbMATH Keywords

contractionAT-free graphsinduced minor

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• Graph minors. XIII: The disjoint paths problem
• Representation of a finite graph by a set of intervals on the real line
• Title not available (Why is that?)
• Asteroidal Triple-Free Graphs
• Partitioning graphs into connected parts
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• 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
• Induced disjoint paths in AT-free graphs
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting induced star-like minors in polynomial time
• On graph contractions and induced minors
• 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
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Contraction checking in graphs on surfaces
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Title not available (Why is that?)

Cited In (4)

• Contracting bipartite graphs to paths and cycles
• Graph editing to a fixed target
• Combing a Linkage in an Annulus
• Contracting bipartite graphs to paths and cycles

This page was built for publication: Detecting induced minors in AT-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390909)