Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Packing non-returnin ...
Conference paper

Packing non-returning A-paths algorithmically

Gyula Pap (1)
(1) Operations Research Department
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3399
License
https://about.hal.science/hal-authorisation-v1
Indicators
613
Views
815
Downloads

Packing non-returning A-paths algorithmically

Gyula Pap (1)
(1) Operations Research Department
Abstract
In this paper we present an algorithmic approach to packing A-paths. It is regarded as a generalization of Edmonds' matching algorithm, however there is the significant difference that here we do not build up any kind of alternating tree. Instead we use the so-called 3-way lemma, which either provides augmentation, or a dual, or a subgraph which can be used for contraction. The method works in the general setting of packing non-returning A-paths. It also implies an ear-decomposition of criticals, as a generalization of the odd ear-decomposition of factor-critical graph.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • A-paths
  • matching
Cited by

Source: OpenCitations

  • Parameterized Complexity of $$(A,\ell )$$-Path Packing

    arXiv (Cornell University)

    Authors : Rémy Belmonte ORCID, Tesshu Hanaka ORCID, Masaaki Kanzaki, Masashi Kiyomi ORCID, Yasuaki Kobayashi ORCID, Yusuke Kobayashi ORCID, Michael Lampis ORCID, Hirotaka Ono ORCID, Yota Otachi ORCID

    Journal reference : Volume , 2020, pp. 43-55

    DOI : 10.1007/978-3-030-48966-3_4

  • A Fast Algorithm for the Path 2-Packing Problem

    Theory of Computing Systems

    Authors : Maxim A. Babenko

    Journal reference : Volume 46, 2008, pp. 59-79

    DOI : 10.1007/s00224-008-9141-y

  • On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints

    SSRN Electronic Journal

    Authors : Susobhan Bandopadhyay ORCID, Aritra Banik ORCID, Diptapriyo Majumdar ORCID, Abhishek Sahu

    Journal reference : Volume , 2026, pp.

    DOI : 10.2139/ssrn.6295237

  • Parameterized Complexity of $$(A,\ell )$$-Path Packing

    Algorithmica

    Authors : Rémy Belmonte ORCID, Tesshu Hanaka ORCID, Masaaki Kanzaki, Masashi Kiyomi ORCID, Yasuaki Kobayashi ORCID, Yusuke Kobayashi ORCID, Michael Lampis ORCID, Hirotaka Ono ORCID, Yota Otachi ORCID

    Journal reference : Volume 84, 2021, pp. 871-895

    DOI : 10.1007/s00453-021-00875-y

  • 0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)

    Authors : Yoichi Iwata ORCID, Yutaro Yamaguchi ORCID, Yuichi Yoshida ORCID

    Journal reference : Volume , 2018, pp. 462-473

    DOI : 10.1109/focs.2018.00051

  • A Fast Algorithm for Path 2-Packing Problem

    Lecture notes in computer science

    Authors : Maxim A. Babenko

    Journal reference : Volume , 2007, pp. 70-81

    DOI : 10.1007/978-3-540-74510-5_10

  • Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity

    SIAM Journal on Discrete Mathematics

    Authors : Yutaro Yamaguchi ORCID

    Journal reference : Volume 30, 2016, pp. 474-492

    DOI : 10.1137/130949877

  • Tree metrics and edge-disjoint $$S$$ S -paths

    Mathematical Programming

    Authors : Hiroshi Hirai ORCID, Gyula Pap ORCID

    Journal reference : Volume 147, 2013, pp. 81-123

    DOI : 10.1007/s10107-013-0713-5

  • Algebraic Algorithms for Linear Matroid Parity Problems

    ACM Transactions on Algorithms

    Authors : Ho Yee Cheung, Lap Chi Lau, Kai Man Leung

    Journal reference : Volume 10, 2014, pp. 1-26

    DOI : 10.1145/2601066

  • Half-integrality, LP-branching, and FPT Algorithms

    SIAM Journal on Computing

    Authors : Yoichi Iwata ORCID, Magnus Wahlström ORCID, Yuichi Yoshida ORCID

    Journal reference : Volume 45, 2016, pp. 1377-1411

    DOI : 10.1137/140962838
Preview
Loading PDF preview...