La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four Énumération efficace des correspondances induites dans un graphique sans cycles de longueur quatre

Kazuhiro KURITA, Kunihiro WASA, Takeaki UNO, Hiroki ARIMURA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Dans cette étude, nous abordons un problème relatif au dénombrement par correspondance induite. Un ensemble de bords M est une correspondance induite d'un graphe G=(V,E). L'énumération des appariements a été largement étudiée dans la littérature ; cependant, il existe peu d'études sur l'appariement induit. Un algorithme simple prend O2) temps pour chaque solution issue du temps nécessaire pour générer un sous-problème, où Δ est le degré maximum dans un graphe d'entrée. Pour générer un sous-problème, un algorithme capte une arête e et génère deux graphiques, celui-ci est obtenu en supprimant e du G, l'autre est obtenu en supprimant e, bord adjacent à e, et les bords adjacents au bord adjacent de e. Puisque cette opération nécessite O2) temps, un algorithme simple énumère toutes les correspondances induites dans O2) temps par solution. Nous avons étudié les structures locales qui nous permettent de générer des sous-problèmes en peu de temps et avons prouvé que la complexité temporelle sera O(1) si le graphique d'entrée est C4-gratuit. Un graphique est C4-free si et seulement si aucun de ses sous-graphes n'a de cycle de longueur quatre.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1383-1391
Date de publication
2018/09/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E101.A.1383
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Kazuhiro KURITA
  Hokkaido University
Kunihiro WASA
  National Institute of Informatics
Takeaki UNO
  National Institute of Informatics
Hiroki ARIMURA
  Hokkaido University

Mots-clés

Table des matières