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.