Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Barnaby Dalton

dblp:129/6098 · DBLP profile ↗
← Back
1ranked-venue papers
0as first author
0since 2021 · last 2013
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Graph algorithms and graph theory · 91% Algorithms and data structures · 9%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Graph algorithms and graph theory › graph classes › perfect graph
cocomparability graphs
0.212013
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs · SIAM J. Comput. 2013
Graph algorithms and graph theory › graph theory › graph covering › path cover
minimum path cover
0.212013
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs · SIAM J. Comput. 2013
Graph algorithms and graph theory › graph theory › graph covering
path cover
0.212013
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs · SIAM J. Comput. 2013
Algorithms and data structures
certifying algorithm
0.012013
LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs · SIAM J. Comput. 2013

Methods — techniques the papers use, named apart from their topics

lexicographic depth first search · 0.2graph search · 0.2
YearPublicationVenuePosition
2013 LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
abstract
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.
Derek G. Corneil, Barnaby Dalton, Michel Habib
SIAM J. Comput.2