Three-in-a-tree in near linear time

DOI10.1145/3357713.3384235MaRDI QIDQ5145012zbMATH OpenOpenAlexFDO

Authors Kai-Yuan Lai, Hsueh-I Lu, Mikkel Thorup

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.07446

zbMATH Keywords

perfect graphSPQR-treedynamic graph algorithmtop treeodd holegraph recognitioneven holeinduced subgraph detection

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(14)

• Finding a shortest even hole in polynomial time
• Even pairs in Berge graphs with no balanced skew-partitions
• FPT and kernelization algorithms for the induced tree problem
• Detecting \(K_{2,3}\) as an induced minor
• Detecting a long even hole
• MIP formulations for induced graph optimization problems: a tutorial
• Detecting a long odd hole
• The three-in-a-tree problem
• Induced minor models. I: Structural properties and algorithmic consequences
• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Three-in-a-Tree in Near Linear Time
• Improved algorithms for perfect graphs and odd holes
• Parameterized max min feedback vertex set

This page was built for publication: Three-in-a-tree in near linear time

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