๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The parity path problem on some subclasses of perfect graphs

โœ Scribed by C.R. Satyan; C.Pandu Rangan

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
560 KB
Volume
68
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A note on the complexity of longest path
A note on the complexity of longest path problems related to graph coloring
โœ P.M. Pardalos; A. Migdalas ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 194 KB

In this note, we show that some problems related to the length of the longest simple path from a given vertex in a graph are NP-complete. We also discuss an extension to the graph coloring problem.

The hardness of perfect phylogeny, feasi
The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
โœ Hans L. Bodlaender; Michael R. Fellows; Michael T. Hallett; H.Todd Wareham; Tand ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 271 KB

In this paper, we consider the complexity of a number of combinatorial problems; namely, INTERVALIZING COLORED GRAPHS (DNA PHYSICAL MAPPING), TRIANGULATING COLORED GRAPHS (PERFECT PHYLOGENY), (DIRECTED) (MODIFIED) COLORED CUTWIDTH, FEASIBLE REGISTER ASSIGNMENT and MODULE ALLOCATION FOR GRAPHS OF BOU

The performance of an eigenvalue bound o
The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
โœ C. Delorme; S. Poljak ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 683 KB

Delorme, C. and S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Mathematics 111 (1993) 145-156. The authors earlier introduced a number q(C), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more