The three-in-a-tree problem

DOI10.1007/S00493-010-2334-4zbMATH Open1231.05246OpenAlexW2104062785MaRDI QIDQ653792FDOQ653792

Authors: Maria Chudnovsky, Paul Seymour 

Publication date: 19 December 2011

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-010-2334-4

Recommendations

• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• Three-in-a-tree in near linear time
• The four-in-a-tree problem in triangle-free graphs
• FPT and kernelization algorithms for the induced tree problem
• Characterization of partial 3-trees in terms of three structures
• scientific article
• On the SPANNING \(k\)-TREE problem
• Finding induced trees
• Testing for a theta
• Complexity of Finding Embeddings in a k-Tree

zbMATH Keywords

induced subgraph testing, theta, pyramid

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)

Cites Work

• Recognizing Berge graphs
• Algorithms for Perfectly Contractile Graphs
• Detecting a Theta or a Prism
• On the complexity of testing for odd holes and induced odd paths

Cited In (39)

• Three tree-paths
• Induced disjoint paths in AT-free graphs
• Testing for a theta
• Title not available (Why is that?)
• Finding a shortest even hole in polynomial time
• The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Exact Solution Algorithms for the Chordless Cycle Problem
• FPT and kernelization algorithms for the induced tree problem
• Detecting a long even hole
• MIP formulations for induced graph optimization problems: a tutorial
• Detecting an induced net subdivision
• Finding an induced subdivision of a digraph
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• A faster algorithm to recognize even-hole-free graphs
• Detecting a Theta or a Prism
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• The four-in-a-tree problem in triangle-free graphs
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Induced disjoint paths in claw-free graphs
• Finding a subdivision of a digraph
• Clique or hole in claw-free graphs
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• The sandwich problem for decompositions and almost monotone properties
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Detecting induced subgraphs
• On the forbidden induced subgraph sandwich problem
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• Faster 3-Coloring of Small-Diameter Graphs
• The \(k\)-in-a-path problem for claw-free graphs
• Large Induced Subgraphs via Triangulations and CMSO
• A class of three-colorable triangle-free graphs
• Every tree is 3-equitable
• Detecting an induced subdivision of \(K_{4}\)
• CIO and ring graphs: deficiency and testing
• Finding induced trees
• A faster algorithm to recognize even-hole-free graphs
• Finding induced paths of given parity in claw-free graphs

This page was built for publication: The three-in-a-tree problem

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