𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the 2-Chain Subgraph Cover and Related Problems

✍ Scribed by T.H. Ma; J.P. Spinrad

Book ID
118204496
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
752 KB
Volume
17
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the complexity of the k-chain subgrap
On the complexity of the k-chain subgraph cover problem
✍ Yu Chang-Wu; Chen Gen-Huey; Ma Tze-Heng πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 776 KB

The k-chain subgraph cover problem asks if the edge set of a given bipartite graph G is the union of the edge sets of k chain graphs, where each chain graph is a subgraph of G. Although the X--chain subgraph cover problem is known to be NP-complete for the class of bipartite graphs, it is still unkn

On partitioning interval graphs into pro
On partitioning interval graphs into proper interval subgraphs and related problems
✍ FrΓ©dΓ©ric Gardi πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

In this paper, we establish that any interval graph (resp. circulararc graph) with n vertices admits a partition into at most log 3 n (resp. log 3 n +1) proper interval subgraphs, for n>1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, t