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

detection algorithminduced subgraphprismthetathree disjoint pathstriangle

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)

• The sandwich problem for decompositions and almost monotone properties
• Detecting a long even hole
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• 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
• Testing for a theta
• Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs
• CIO and ring graphs: deficiency and testing
• A faster algorithm to recognize even-hole-free graphs
• Finding a shortest even hole in polynomial time
• Partial characterizations of circle graphs
• The three-in-a-tree problem

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)