A linear kernel for finding square roots of almost planar graphs

DOI10.4230/LIPICS.SWAT.2016.4MaRDI QIDQ5369506zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart

Publication date 17 October 2017

Full work available at URL https://dx.doi.org/10.4230/LIPIcs.SWAT.2016.4

zbMATH Keywords

linear kernelplanar graphssquare roots

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A linear kernel for finding square roots of almost planar graphs
• Parameterized algorithms for finding square roots
• Computing square roots of graphs with low maximum degree
• Graph square roots of small distance from degree one graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

Cited in

(6)

• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Finding cactus roots in polynomial time
• Squares of low clique number
• Graph square roots of small distance from degree one graphs
• Graph square roots of small distance from degree one graphs

This page was built for publication: A linear kernel for finding square roots of almost planar graphs

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