Our main result is a linear-time (that is, time O(m+n)) algorithm to recognize and represent
proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time …

Graph theory was founded by Euler [78] in 1736 as a generalization to the solution of the
famous problem of the Könisberg bridges. From 1736 to 1936, the same concept as graph …

The increasing concern over global warming has led to the rapid development of the electric
vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect …

A matching in a graph is a set of edges no two of which share a common vertex. A matching
M is an induced matching if no edge connects two edges of M. The problem of finding a …

This paper first presents a unified approach to design efficient algorithms for the weighted
domination problem and its three variants, ie, the weighted independent, connected, and …

To cover the edges of a graph with a minimum number of cliques is an NP-hard problem
with many applications. For this problem we develop efficient and effective polynomial-time …

Given a graph in any of the following graph classes: trapezoid graphs, circular permutation
graphs, convex graphs, Dilworth k graphs, k-polygon graphs, circular arc graphs and …

In the Edge Clique Cover (ecc) problem, given an undirected graph G and an integer k, we
ask whether one can choose k cliques in G such that each edge of G is contained in at least …

Circular-arc graphs have a rich combinatorial structure. The circular endpoint sequence of
arcs in a model for a circular-arc graph is usually far from unique. We present a natural …

To monitor an electric power system by placing as few phase measurement units (PMUs) as
possible is closely related to the famous vertex cover problem and domination problem in …