Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
On maximum induced matchings in bipartite graphs
Autore:
Lozin, VV;
Indirizzi:
Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA Rutgers State Univ Piscataway NJ USA 08854 TCOR, Piscataway, NJ 08854 USA
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 1, volume: 81, anno: 2002,
pagine: 7 - 11
SICI:
0020-0190(20020116)81:1<7:OMIMIB>2.0.ZU;2-6
Fonte:
ISI
Lingua:
ENG
Keywords:
graph algorithms; computational complexity; maximum induced matching; bipartite graphs;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
7
Recensione:
Indirizzi per estratti:
Indirizzo: Lozin, VV Rutgers State Univ, RUTCOR, 640 Bartholomew Rd, Piscataway, NJ 08854 USA Rutgers State Univ 640 Bartholomew Rd Piscataway NJ USA 08854 SA
Citazione:
V.V. Lozin, "On maximum induced matchings in bipartite graphs", INF PROCESS, 81(1), 2002, pp. 7-11

Abstract

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C-4-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs. (C) 2002 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 20/01/20 alle ore 07:45:04