Linear Time LexDFS on Cocomparability Graphs.

DOI10.1007/978-3-319-08404-6_28zbMath1417.68162arXiv1404.5996OpenAlexW2144199330MaRDI QIDQ3188906

Ekkehard Köhler, Lalla Mouatadid

Publication date: 2 September 2014

Published in: Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

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

zbMATH Keywords

posetsHamiltonian pathcocomparability graphsgraph searchinglexicographic depth first search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Robinsonian matrices: recognition challenges ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Unnamed Item ⋮ A new graph parameter to measure linearity ⋮ Counting independent sets in cocomparability graphs ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ The Recognition Problem of Graph Search Trees ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

This page was built for publication: Linear Time LexDFS on Cocomparability Graphs.