Elaine M. Eschen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Elaine M. Eschen has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Chinh T. Hoang
Department of Computer Science and Physics Wilfrid Laurier University Waterloo N2L 3C5 Ontario Canada
8 shared publications - R. Sritharan
Computer Science Department, The University of Dayton, Dayton, OH 45469, United States
6 shared publications - Jeremy Spinrad
Vanderbilt University
3 shared publications - Lorna Stewart
Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8
2 shared publications R. Sritharan
2 shared publications- R. Sritharan
Computer Science Department, The University of Dayton, Dayton, OH 45469-2160, USA
2 shared publications
Latest Publications
- 15 October 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 359, 419-424
On some classes of quasi-triangulated graphs
- 15 October 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 359, 419-424
On some classes of quasi-triangulated graphs
- 6 May 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 318, 97-112
Bipartite completion of colored graphs avoiding chordless cycles of given lengths
- 6 May 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 318, 97-112
Bipartite completion of colored graphs avoiding chordless cycles of given lengths
- 1 May 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 223, 39-51
Completing colored graphs to meet a target property
- 1 May 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 223, 39-51
Completing colored graphs to meet a target property
- Open Access
Algorithms for Unipolar and Generalized Split Graphs
A graph $G=(V,E)$ is a {\it unipolar graph} if there exits a partition $V=V_1 \cup V_2$ such that, $V_1$ is a clique and $V_2$ induces the disjoint union of cliques. The complement-closed class of {\it generalized split graphs} are those graphs $G$ such that either $G$ {\it or} the complement of $G$ is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all $C_5$-free (and hence, almost all perfect graphs) are generalized split graphs. In this paper we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time O($nm^\prime$), where $m^\prime$ is the number of edges in a minimal triangulation of the given graph. Generalized split graphs can recognized via this algorithm in O($nm' + n\OL{m}'$) = O($n^3$) time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in O($n+m$) time and for finding a maximum clique and a minimum proper coloring in O($n^{2.5}/\log n$), when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bound. We also prove that the perfect code problem is NP-Complete for unipolar graphs.Open AccessAlgorithms for Unipolar and Generalized Split Graphs
A graph $G=(V,E)$ is a {\it unipolar graph} if there exits a partition $V=V_1 \cup V_2$ such that, $V_1$ is a clique and $V_2$ induces the disjoint union of cliques. The complement-closed class of {\it generalized split graphs} are those graphs $G$ such that either $G$ {\it or} the complement of $G$ is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all $C_5$-free (and hence, almost all perfect graphs) are generalized split graphs. In this paper we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time O($nm^\prime$), where $m^\prime$ is the number of edges in a minimal triangulation of the given graph. Generalized split graphs can recognized via this algorithm in O($nm' + n\OL{m}'$) = O($n^3$) time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in O($n+m$) time and for finding a maximum clique and a minimum proper coloring in O($n^{2.5}/\log n$), when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bound. We also prove that the perfect code problem is NP-Complete for unipolar graphs. - 1 May 2011
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 28 (3) , 347-364
Finding a Sun in Building-Free Graphs
- 1 May 2011
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 28 (3) , 347-364
Finding a Sun in Building-Free Graphs
- 28 March 2011
- Published by Elsevier in Discrete Mathematics
- Vol. 311 (6) , 431-434
On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
- 28 March 2011
- Published by Elsevier in Discrete Mathematics
- Vol. 311 (6) , 431-434
On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
- Open Access
Finding a sun in building-free graphs
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.
Open AccessFinding a sun in building-free graphs
Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete. We show that whether a building-free graph contains a sun can be decided in O(min$\{m{n^3}, m^{1.5}n^2\}$) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.
- Open Access
On graphs without a C4 or a diamond
We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C4, diamond)-free graph and the number of n-vertex, labeled (C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.
Open AccessOn graphs without a C4 or a diamond
We consider the class of (C4, diamond)-free graphs; graphs in this class do not contain a C4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C4, diamond)-free graph and the number of n-vertex, labeled (C4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs.
- Open Access
On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
In an article [3] published recently in this journal, it was shown that when k >= 3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k = 2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism but no harder than graph isomorphism.
Open AccessOn the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
In an article [3] published recently in this journal, it was shown that when k >= 3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k = 2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism but no harder than graph isomorphism.
- 20 February 2008
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 30, 291-296
2K2 vertex-set partition into nonempty parts
- 20 February 2008
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 30, 291-296
2K2 vertex-set partition into nonempty parts