2 Search Results for "Takazawa, Kenjiro"

Document
DOI: 10.4230/LIPIcs.MFCS.2018.12
The b-Branching Problem in Digraphs

Authors: Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper, we introduce the concept of b-branchings in digraphs, which is a generalization of branchings serving as a counterpart of b-matchings. Here b is a positive integer vector on the vertex set of a digraph, and a b-branching is defined as a common independent set of two matroids defined by b: an arc set is a b-branching if it has at most b(v) arcs sharing the terminal vertex v, and it is an independent set of a certain sparsity matroid defined by b. We demonstrate that b-branchings yield an appropriate generalization of branchings by extending several classical results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b-branching. We then prove a packing theorem extending Edmonds' disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b-branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b-branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b(v) arcs sharing the terminal vertex v.
Cite as

Naonori Kakimura, Naoyuki Kamiyama, and Kenjiro Takazawa. The b-Branching Problem in Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kakimura_et_al:LIPIcs.MFCS.2018.12,
  author =	{Kakimura, Naonori and Kamiyama, Naoyuki and Takazawa, Kenjiro},
  title =	{{The b-Branching Problem in Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.12},
  URN =		{urn:nbn:de:0030-drops-95948},
  doi =		{10.4230/LIPIcs.MFCS.2018.12},
  annote =	{Keywords: Greedy Algorithm, Packing, Matroid Intersection, Sparsity Matroid, Arborescence}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.87
Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs

Authors: Kenjiro Takazawa

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We introduce a new framework of restricted 2-matchings close to Hamilton cycles. For an undirected graph (V,E) and a family U of vertex subsets, a 2-matching F is called U-feasible if, for each setU in U, F contains at most |setU|-1 edges in the subgraph induced by U. Our framework includes C_{<=k}-free 2-matchings, i.e., 2-matchings without cycles of at most k edges, and 2-factors covering prescribed edge cuts, both of which are intensively studied as relaxations of Hamilton cycles. The problem of finding a maximum U-feasible 2-matching is NP-hard. We prove that the problem is tractable when the graph is bipartite and each setU in U induces a Hamilton-laceable graph. This case generalizes the C_{<=4}-free 2-matching problem in bipartite graphs. We establish a min-max theorem, a combinatorial polynomial-time algorithm, and decomposition theorems by extending the theory of C_{<=4}-free 2-matchings. Our result provides the first polynomially solvable case for the maximum C_{<=k}-free 2-matching problem for k >= 5. For instance, in bipartite graphs in which every cycle of length six has at least two chords, our algorithm solves the maximum C_{<=6}-free 2-matching problem in O(n^2 m) time, where n and m are the numbers of vertices and edges, respectively.
Cite as

Kenjiro Takazawa. Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{takazawa:LIPIcs.MFCS.2016.87,
  author =	{Takazawa, Kenjiro},
  title =	{{Finding a Maximum 2-Matching Excluding Prescribed Cycles in Bipartite Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.87},
  URN =		{urn:nbn:de:0030-drops-64950},
  doi =		{10.4230/LIPIcs.MFCS.2016.87},
  annote =	{Keywords: optimization algorithms, matching theory, traveling salesman problem, restricted 2-matchings, Hamilton-laceable graphs}
}
  • Refine by Author
  • 2 Takazawa, Kenjiro
  • 1 Kakimura, Naonori
  • 1 Kamiyama, Naoyuki

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 Arborescence
  • 1 Greedy Algorithm
  • 1 Hamilton-laceable graphs
  • 1 Matroid Intersection
  • 1 Packing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact