The three-in-a-tree problem

DOI10.1007/S00493-010-2334-4MaRDI QIDQ653792zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

induced subgraph testing, theta, pyramid

Mathematics Subject Classification ID

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

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; zbMATH DE number 3866594
• On the SPANNING k-TREE problem
• Finding induced trees
• Testing for a theta
• Complexity of Finding Embeddings in a k-Tree

Cites work

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

Cited in

(37)

• Three tree-paths
• Testing for a theta
• Faster 3-coloring of small-diameter graphs
• scientific article; zbMATH DE number 4031768 (Why is no real title available?)
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Finding a shortest even hole in polynomial time
• Exact Solution Algorithms for the Chordless Cycle Problem
• FPT and kernelization algorithms for the induced tree problem
• Detecting a long even hole
• Detecting an induced net subdivision
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• MIP formulations for induced graph optimization problems: a tutorial
• A faster algorithm to recognize even-hole-free graphs
• Detecting a Theta or a Prism
• The four-in-a-tree problem in triangle-free graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• 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
• The sandwich problem for decompositions and almost monotone properties
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• The \(k\)-in-a-tree problem for chordal graphs
• On the forbidden induced subgraph sandwich problem
• Integer programming formulations for the \(k\)-in-a-tree problem in 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
• CIO and ring graphs: deficiency and testing
• Detecting an induced subdivision of \(K_{4}\)
• 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)