Detecting a Theta or a Prism

DOI10.1137/060672613zbMath1181.05081OpenAlexW2121603419MaRDI QIDQ3394995

Rohan Kapadia, Maria Chudnovsky

Publication date: 20 August 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/060672613

zbMATH Keywords

triangleprisminduced subgraphthetadetection algorithmthree disjoint paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Detecting a long even hole ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs ⋮ Finding a shortest even hole in polynomial time ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Partial characterizations of circle graphs ⋮ The three-in-a-tree problem ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ CIO and ring graphs: deficiency and testing ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Unnamed Item

This page was built for publication: Detecting a Theta or a Prism