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

zbMATH Keywords

graph algorithmscocomparability graphspartial orderscomparability graphslinear extensionsLDFSlexicographic depth-first searchclassical graph searchesminimum path cover problemrecognition of permutation graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ A tie-break model for graph search ⋮ Unnamed Item ⋮ A new graph parameter to measure linearity ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

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(n^alpha)
• 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