1,721,012 research outputs found
A Superclass of Edge-Path-Tree graphs with few cliques
Get PDFEdge-Path-Tree graphs are intersection graphs of Edge-Path-Tree matrices that is matrices whose columns are incidence vectors of edge-sets of paths in a given tree. Edge-Path-Tree
graphs have polynomially many cliques as proved in [4] and [7]. Therefore, the problem of finding a clique of maximum weight in these graphs is solvable in strongly polynomial time.
In this paper we extend this result to a proper superclass of Edge-Path-Tree graphs. Each graph in the class is defined as the intersection graph of a matrix with no submatrix in a set W of seven small forbidden submatrices. By forbidding an eighth small matrix, our result
specializes to Edge-Path-Tree graph
Recognizing Helly edge path tree graphs and their clique graphs
No full textWe present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 822] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs
Mengerian quasi-graphical families and clutters
No full textBalanceable clutters are clutters whose bipartite representation contains no odd wheel and no odd 3-path configuration as an induced subgraph (this is Truemper’s characterization of balanceable matrices). In this paper we study a proper subclass of balanceable clutters called quasi-graphical defined by forbidding one-sided even wheels and one-sided even 3-path configurations. We characterize Mengerian quasi-graphical clutters and, as a consequence, we show that a recent conjecture in Cornuéjols et al. (2000) [7] is true for quasi-graphical clutters
On a Facility Location Problem with Applications to Tele-Diagnostic
No full textConsider an undirected graph G modelling a network. Each vertex in the graph contains some physical devices, which can be monitored and possibly repaired from a remote site in case they become faulty. We assume that there can be two kinds of faults in the system: soft faults, which can be repaired remotely from another site (i.e., a monitor), and severe faults which cannot be repaired remotely and require further (possibly human) interventions. We assume that soft faults happen with some fixed probability λ, 0 < λ ≤ 1. We investigate the problem of locating monitors in the network so as to minimize the total expected communication cost per fault. We formalize such a problem as a location problem with a cost function depending on λ and study some properties of the optimal solutions. The latter are exploited for investigating the complexity of the problem and providing efficient approximation algorithms
- …
