Detecting a Theta or a Prism

DOI10.1137/060672613MaRDI QIDQ3394995zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Rohan Kapadia

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 subgraphdetection algorithmthetathree disjoint paths

Mathematics Subject Classification ID

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

Recommendations

• Testing for a theta
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• The three-in-a-tree problem
• Graphs with polynomially many minimal separators
• The (theta, wheel)-free graphs. IV: Induced paths and cycles

Cited in

(12)

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

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

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