The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs

DOI10.23638/DMTCS-22-4-13zbMath1462.05336arXiv1904.08076MaRDI QIDQ4987262

Shou-Jun Xu, Xiaolu Gao

Publication date: 3 May 2021

Full work available at URL: https://arxiv.org/abs/1904.08076

zbMATH Keywords

girthcocomparability graphdiamond-free graph\(\overline{P_2 \cup P_3}\)-freeLBFS+LexCycle

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• A new LBFS-based algorithm for cocomparability graph recognition
• LexBFS-orderings and powers of chordal graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A new graph parameter to measure linearity
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• On the Power of Graph Searching for Cocomparability Graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• The LBFS Structure and Recognition of Interval Graphs
• Domination on Cocomparability Graphs
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs

This page was built for publication: The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs