Result: Structure theorem and algorithm on (1, f)-odd subgraph
Title:
Structure theorem and algorithm on (1, f)-odd subgraph
Authors:
Source:
The Fourth Cracow Conference on Graph Theory Czorsztyn 2002Discrete mathematics. 307(11-12):1404-1417
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 7 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Recherche information. Graphe, Information retrieval. Graph, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Factorisation, Factorization, Factorización, Sous graphe, Subgraph, Subgrafo, 68R10, 68Wxx, Algorithme polynomial, Preuve, Problème gap, Gap problem, (1, f)-odd subgraphs; Gallai-Edmonds type structure theorem; Generalized matching algorithm
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer and Information Sciences, Ibaraki University, Hitachi, Ibaraki 316-8511, Japan
Department of Computer and Information Sciences, Budapest University of Technology and Economics, 1364, Hungary
Department of Computer and Information Sciences, Budapest University of Technology and Economics, 1364, Hungary
ISSN:
0012-365X
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.18660651
Database:
PASCAL Archive
Further Information
The authors give a Gallai-Edmonds type structure theorem on (1, f)-odd subgraphs and a polynomial algorithm for finding an optimal (1, f)-odd subgraph. Lovász [The factorization of graphs. II. Acta Math. Acad. Sci. Hungar. 23 (1972) 223-246] and Cornuéjols [General factors of graphs, J. Combin. Theory Ser. B 45(2) (1988) 185-198] solved these problems for a more general problem, the general factor problem with gaps at most 1. However, the statements of the theorems and the algorithm are much more simple in this special case, so it is worth of interest on its own. Also, the algorithm given for this case is faster than the general algorithm. The proofs follow a direct approach instead of deducing from the general case.