LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
| Autor: | Derek G. Corneil, Michel Habib, Barnaby Dalton |
|---|---|
| Přispěvatelé: | Department of Computer Science [University of Toronto] (DCS), University of Toronto, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria) |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) General Computer Science General Mathematics 010102 general mathematics [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0102 computer and information sciences Path cover 01 natural sciences Longest path problem Combinatorics Indifference graph Pathwidth 010201 computation theory & mathematics Chordal graph Maximal independent set 0101 mathematics Algorithm Hamiltonian path problem Mathematics MathematicsofComputing_DISCRETEMATHEMATICS AMS 05C85 05C38 05C62 68R10 |
| Zdroj: | SIAM Journal on Computing SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2013, 42 (3), pp.792-807. ⟨10.1137/11083856X⟩ SIAM Journal on Computing, 2013, 42 (3), pp.792-807. ⟨10.1137/11083856X⟩ |
| ISSN: | 0097-5397 |
| DOI: | 10.1137/11083856X⟩ |
| Popis: | International audience; For graph $G(V,E)$, a minimum path cover (MPC) is a minimum cardinality set of vertex disjoint paths that cover $V$ (i.e., every vertex of $G$ is in exactly one path in the cover). This problem is a natural generalization of the Hamiltonian path problem. Cocomparability graphs (the complements of graphs that have an acyclic transitive orientation of their edge sets) are a well studied subfamily of perfect graphs that includes many popular families of graphs such as interval, permutation, and cographs. Furthermore, for every cocomparability graph $G$ and acyclic transitive orientation of the edges of $\overline{G}$ there is a corresponding poset $P_G$; it is easy to see that an MPC of $G$ is a linear extension of $P_G$ that minimizes the bump number of $P_G$. Although there are directly graph-theoretical MPC algorithms (i.e., algorithms that do not rely on poset formulations) for various subfamilies of cocomparability graphs, notably interval graphs, until now all MPC algorithms for cocomparability graphs themselves have been based on the bump number algorithms for posets. In this paper we present the first directly graph-theoretical MPC algorithm for cocomparability graphs; this algorithm is based on two consecutive graph searches followed by a certifying algorithm. Surprisingly, except for a lexicographic depth first search (LDFS) preprocessing step, this algorithm is identical to the corresponding algorithm for interval graphs. The running time of the algorithm is $O({\rm min}(n^2, n + {\rm mloglogn}))$, with the nonlinearity coming from LDFS. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|