Fast Algorithms forK4Immersion Testing

DOI10.1006/JAGM.1998.0991MaRDI QIDQ4238533zbMATH OpenOpenAlexFDO

Authors Heather Booth, Rajeev Govindan, Michael A. Langston, Siddharthan Ramachandramurthi

Publication date 30 March 1999

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1998.0991

zbMATH Keywords

undirected graph

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A weak immersion relation on graphs and its applications
• Detecting an induced subdivision of \(K_{4}\)
• Induced immersions
• Finding topological subgraphs is fixed-parameter tractable
• Detecting an induced subdivision of K₄

Cited in

(8)

• Structure and recognition of graphs with no 6-wheel subdivision
• A note on immersion minors and planarity
• A faster test for 4-flow-criticality in snarks
• A minimum degree condition forcing complete graph immersion
• Complete graph immersions in dense graphs
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• List-coloring graphs without subdivisions and without immersions
• The structure of graphs with no W4 immersion

This page was built for publication: Fast Algorithms forK4Immersion Testing

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