2004 | OriginalPaper | Buchkapitel
Minsquare Factors and Maxfix Covers of Graphs
verfasst von : Nicola Apollonio, András Sebő
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We provide a polynomial algorithm that determines for any given undirected graph, positive integer k and various objective functions on the edges or on the degree sequences, as input, k edges that minimize the given objective function. The tractable objective functions include linear, sum of squares, etc. The source of our motivation and at the same time our main application is a subset of k vertices in a line graph, that cover as many edges as possible (maxfix cover). Besides the general algorithm and connections to other problems, the extension of the usual improving paths for graph factors could be interesting in itself: the objects that take the role of the improving walks for b-matchings or other general factorization problems turn out to be edge-disjoint unions of pairs of alternating walks. The algorithm we suggest also works if for any subset of vertices upper, lower bound constraints or parity constraints are given. In particular maximum (or minimum) weight b-matchings of given size can be determined in polynomial time, combinatorially, in more than one way.