On the Power of Graph Searching for Cocomparability Graphs
DOI10.1137/15M1012396zbMath1333.05285OpenAlexW4299324743MaRDI QIDQ2801333
Jérémie Dusart, Ekkehard Köhler, Derek Gordon Corneil, Michel A. Habib
Publication date: 7 April 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1012396
graph algorithmscocomparability graphspartial orderscomparability graphslinear extensionsLDFSlexicographic depth-first searchclassical graph searchesminimum path cover problemrecognition of permutation graphs
Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- NP-completeness properties about linear extensions
- The longest path problem has a polynomial solution on interval graphs
- Some aspects of perfect elimination orderings in chordal graphs
- On the greedy dimension of a partial order
- Linear algorithm for optimal path cover problem on interval graphs
- An optimal greedy heuristic to color interval graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Paths in interval graphs and circular arc graphs
- Modular decomposition and transitive orientation
- LexBFS-orderings and powers of chordal graphs
- Efficient graph representations
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Algorithmic graph theory and perfect graphs
- Optimal greedy algorithms for indifference 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
- Linear Time LexDFS on Cocomparability Graphs.
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- BetweenO(nm) andO(nalpha)
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- A Unified View of Graph Searching
- Algorithmic Aspects of Vertex Elimination on Graphs
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
- Depth-First Search and Linear Graph Algorithms
- A Dual of Dilworth's Decomposition Theorem
This page was built for publication: On the Power of Graph Searching for Cocomparability Graphs