Polar permutation graphs are polynomial-time recognisable

DOI10.1016/J.EJC.2011.12.007MaRDI QIDQ1933641zbMATH OpenOpenAlexFDO

Authors Tınaz Ekim, Pinar Heggernes, Daniel Meister

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

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)

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

Cited in

(10)

• On opposition graphs, coalition graphs, and bipartite permutation graphs
• Algorithms for unipolar and generalized split graphs
• Generalized coloring of permutations
• Generalized Coloring of Permutations
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Relaxation of the famous NP-complete polar graphs recognition problem leading to the fast polynomial-time algorithm
• Partitioning a graph into disjoint cliques and a triangle-free graph
• Polar permutation graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• Recognizing polar planar graphs using new results for monopolarity

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)