Polar permutation graphs are polynomial-time recognisable

DOI10.1016/J.EJC.2011.12.007zbMATH Open1257.05127OpenAlexW2083238533MaRDI QIDQ1933641FDOQ1933641

Daniel Meister, Pinar Heggernes, Tınaz Ekim

Publication date: 24 January 2013

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2011.12.007

Recommendations

• Polar permutation graphs
• Polar cographs
• Relaxation of the famous NP-complete polar graphs recognition problem leading to the fast polynomial-time algorithm
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Polar cographs

zbMATH Keywords

bipartite graphssplit graphsmatrix partitionscobipartite graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (6)

• Generalized coloring of permutations
• Generalized Coloring of Permutations
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Algorithms for unipolar and generalized split graphs
• Polar permutation graphs
• Complexity and algorithms for recognizing polar and monopolar graphs

This page was built for publication: Polar permutation graphs are polynomial-time recognisable

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