z-logo
Premium
On the Complexity of Computing the Excessive [ B ]‐Index of a Graph
Author(s) -
Cariolaro David,
Rizzi Romeo
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21887
Subject(s) - mathematics , factorization , combinatorics , graph , discrete mathematics , integer (computer science) , algorithm , computer science , programming language
Let B be a positive integer and let G be a simple graph. An excessive [ B ]‐factorization of G is a minimum set of matchings, each of size B , whose union is E ( G ) . The number of matchings in an excessive [ B ]‐factorization of G (or ∞ if an excessive [ B ]‐factorization does not exist) is a graph parameter called the excessive [ B ]‐ index of G and denoted byχ [ B ] ′ ( G ) . In this article we prove that, for any fixed value of B , the parameterχ [ B ] ′ ( G )can be computed in polynomial time in the size of the graph G . This solves a problem posed by one of the authors at the 21st British Combinatorial Conference.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here