Polar permutation graphs

DOI10.1007/978-3-642-10217-2_23MaRDI QIDQ3651548zbMATH OpenOpenAlexFDO

Authors Tınaz Ekim, Pinar Heggernes, Daniel Meister

Publication date 11 December 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-10217-2_23

zbMATH Keywords

bipartite graphscomplete multipartite graphpermutation graphspolynomial time algorithmsplit graphsmatrix partitionspolar graphscobipartite graphsdisjoint union of complete graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75)

Recommendations

• Polar permutation graphs are polynomial-time recognisable
• Polar cographs
• Polar cographs
• scientific article; zbMATH DE number 3966134
• Recognizing line-polar bipartite graphs in time \(O(n)\)

Cited in

(10)

• Relaxation of the famous NP-complete polar graphs recognition problem leading to the fast polynomial-time algorithm
• scientific article; zbMATH DE number 3966134 (Why is no real title available?)
• List monopolar partitions of claw-free graphs
• Recognizing line-polar bipartite graphs in time \(O(n)\)
• Minimal obstructions to ( , k )-polarity in cographs
• Solving partition problems with colour-bipartitions
• A forbidden subgraph characterization of line-polar bipartite graphs
• Polar permutation graphs are polynomial-time recognisable
• Monopolar graphs: complexity of computing classical graph parameters
• Polar cographs

This page was built for publication: Polar permutation graphs

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