|
[1]
|
Márton Makai.
Matroid matching with dilworth truncation.
Discrete Mathematics, 308(8):1394-1404, 2008.
[ bib ]
|
|
[2]
|
Márton Makai and Jácint Szabó.
The parity problem of polymatroids without double circuits.
Combinatorica, 28(6):679-692, 2008.
[ bib ]
|
|
[3]
|
Márton Makai.
On maximum cost Kt, t-free t-matchings of bipartite
graphs.
SIAM J. Discrete Math., 21(2):349-360, 2007.
[ bib ]
|
|
[4]
|
Márton Makai.
Matroid matching: a new class of matroids possessing the double
circuit property.
2006.
submitted.
[ bib ]
|
|
[5]
|
Márton Makai.
Reroute sequence planning in telecommunication networks and compact
vector summation.
Applied Mathematics and Computation, 150(3):785-801, 2004.
[ bib |
.ps ]
|
|
[6]
|
Balázs Gábor Józsa and Márton Makai.
On the solution of reroute sequence planning problem in MPLS
networks.
Computer Networks, 42(2):199-210, 2003.
[ bib |
.ps ]
|
|
[7]
|
Tamás Király and Márton Makai.
Connectivity augmentation problems of directed hypergraphs.
Mat. Lapok (N.S.), 13(1):32-39, 2006/07.
[ bib ]
|
|
[1]
|
Márton Makai, Gyula Pap, and Jácint Szabó.
Matching problems in polymatroids without double circuits.
In IPCO, pages 167-181, 2007.
[ bib ]
|
|
[2]
|
Mihály Bárász, Zsolt Fekete, Alpár Jüttner, Márton Makai, and
Jácint Szabó.
Qos aware and fair resource allocation scheme in transport networks.
In 8th International Conference on Transparent Optical Networks
(ICTON), Nottingham, United Kingdom, June 2006.
[ bib |
.pdf ]
|
|
[3]
|
Márton Makai.
Rigid graphs from edge-pairs.
In 4th Japanese-Hungarian Symposium on Discrete Mathematics and
Its Applications, pages 199-208, June 2005.
[ bib ]
|
|
[4]
|
Márton Makai.
Matroid matching with Dilworth truncation.
In Stefan Felsner, editor, 2005 European Conference on
Combinatorics, Graph Theory and Applications (EuroComb '05), volume AE of
DMTCS Proceedings, pages 175-180. Discrete Mathematics and Theoretical
Computer Science, 2005.
[ bib |
.html ]
Let H=(V,E) be a hypergraph and let k>=1
and l>=0
be fixed integers. Let M be the
matroid
with ground-set E s.t. a set FE
is
independent if and only if each XV with
k|X|-l>=0
spans at most k|X|-l hyperedges of F. We
prove that if
H is dense enough, then M
satisfies
the double circuit property, thus the min-max formula of Dress and
Lovász on the
maximum matroid matching holds for M.
Our
result implies the Berge-Tutte formula on the maximum matching of
graphs
(k=1, l=0), generalizes Lovász'
graphic
matroid (cycle matroid) matching formula to hypergraphs
(k=l=1)
and gives a min-max formula for the maximum matroid matching in the
2-dimensional
rigidity matroid (k=2, l=3).
Keywords: matroid matching, Dilworth truncation, double circuit property
|
|
[5]
|
Tamás Király and Márton Makai.
On polyhedra related to even factors.
In IPCO, volume 3064 of Lecture Notes in Computer
Science, pages 416-430. Springer, 2004.
[ bib ]
|
|
[6]
|
Márton Makai.
A polyhedral approach to even factors.
In J. Fiala, editor, 2003 European Conference on Combinatorics,
Graph Theory and Applications (EuroComb '03), pages 259-263, September
2003.
[ bib ]
|
|
[1]
|
Márton Makai and Jácint Szabó.
The parity problem of polymatroids without double circuits.
Technical Report TR-2006-08, MTA-ELTE Egerváry Research Group on
Combinatorial Optimization, 2006.
[ bib |
.ps ]
|
|
[2]
|
Márton Makai.
Matroid matching with Dilworth truncation.
Technical Report TR-2005-11, MTA-ELTE Egerváry Research Group on
Combinatorial Optimization, 2005.
[ bib |
.ps ]
|
|
[3]
|
Márton Makai.
A polyhedral approach to even factors.
Technical Report TR-2003-05, MTA-ELTE Egerváry Research Group on
Combinatorial Optimization, 2003.
[ bib |
.ps ]
|
|
[4]
|
Tamás Király and Márton Makai.
On polyhedra related to even factors.
Technical Report TR-2003-09, MTA-ELTE Egerváry Research Group on
Combinatorial Optimization, 2003.
[ bib |
.ps ]
|
|
[5]
|
Tamás Király and Márton Makai.
A note on hypergraph connectivity augmentation.
Technical Report TR-2002-11, MTA-ELTE Egerváry Research Group on
Combinatorial Optimization, 2002.
[ bib |
.ps ]
|