Recognizing line-polar bipartite graphs in time \(O(n)\)

DOI10.1016/j.dam.2010.05.019zbMath1201.05094OpenAlexW2082569465MaRDI QIDQ602675

Jing Huang, Tınaz Ekim

Publication date: 5 November 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.05.019

zbMATH Keywords

polar graphline-polar graphlinear time recognition algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

List monopolar partitions of claw-free graphs ⋮ Complexity and algorithms for recognizing polar and monopolar graphs ⋮ On the Polarity and Monopolarity of Graphs ⋮ A forbidden subgraph characterization of line-polar bipartite graphs ⋮ Algorithms for unipolar and generalized split graphs ⋮ Solving partition problems with colour-bipartitions

Cites Work

• Unnamed Item
• Unnamed Item
• Polarity of chordal graphs
• A forbidden subgraph characterization of line-polar bipartite graphs
• About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs
• Line-Polar Graphs: Characterization and Recognition
• Polar Permutation Graphs
• Polar cographs