Yusuke Kobayashi

Ryoga Mahara

Souta Sakamoto

Theor. Comput. Sci., 2025

2024

Envy-free relaxations for goods, chores, and mixed items.

[BibT_eX]

[DOI]

Erika R. Bérczi-Kovács

Endre Boros

Fekadu Tolessa Gedefa

Theor. Comput. Sci., 2024

Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem.

[BibT_eX]

[DOI]

Takashi Noguchi

CoRR, 2024

Finding Spanning Trees with Perfect Matchings.

[BibT_eX]

[DOI]

CoRR, 2024

Subquadratic Submodular Maximization with a General Matroid Constraint.

[BibT_eX]

[DOI]

Tatsuya Terao

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Finding a Maximum Restricted t-Matching via Boolean Edge-CSP.

[BibT_eX]

[DOI]

Yuni Iwamasa

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

On reachable assignments under dichotomous preferences.

[BibT_eX]

[DOI]

Theor. Comput. Sci., November, 2023

Feedback vertex set reconfiguration in planar graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., November, 2023

Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints.

[BibT_eX]

[DOI]

Algorithmica, September, 2023

Fixed-parameter algorithms for graph constraint logic.

[BibT_eX]

[DOI]

Theor. Comput. Sci., May, 2023

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, January, 2023

Trade-offs among degree, diameter, and number of paths.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2023

Algorithmic Theory of Qubit Routing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

Reconfiguration of Time-Respecting Arborescences.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 18th International Symposium, 2023

An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover.

[BibT_eX]

[DOI]

Takashi Noguchi

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Reconfiguration of the Union of Arborescences.

[BibT_eX]

[DOI]

Ryoga Mahara

Tamás Schwarcz

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Optimal General Factor Problem and Jump System Intersection.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Rerouting Planar Curves and Disjoint Paths.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Reconfiguration of Colorings in Triangulations of the Sphere.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2022

A Weighted Linear Matroid Parity Algorithm.

[BibT_eX]

[DOI]

Satoru Iwata

SIAM J. Comput., 2022

A parameterized view to the robust recoverable base problem of matroids under structural uncertainty.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2022

An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2022

Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles.

[BibT_eX]

[DOI]

Math. Program., 2022

Submodular reassignment problem for reallocating agents to tasks with synergy effects.

[BibT_eX]

[DOI]

Discret. Optim., 2022

Linear-Time Recognition of Double-Threshold Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2022

Parameterized Complexity of (A, ℓ )-Path Packing.

[BibT_eX]

[DOI]

Algorithmica, 2022

Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

One-Face Shortest Disjoint Paths with a Deviation Terminal.

[BibT_eX]

[DOI]

Tatsuya Terao

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average.

[BibT_eX]

[DOI]

Ryoga Mahara

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Reforming an Envy-Free Matching.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Algorithms for gerrymandering over graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Finding a maximum minimal separator: Graph classes and fixed-parameter tractability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Market Pricing for Matroid Rank Valuations.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Tight Approximation for Unconstrained XOS Maximization.

[BibT_eX]

[DOI]

Math. Oper. Res., 2021

Improved Analysis of Highest-Degree Branching for Feedback Vertex Set.

[BibT_eX]

[DOI]

Yoichi Iwata

Algorithmica, 2021

Computing the Largest Bond and the Maximum Connected Cut of a Graph.

[BibT_eX]

[DOI]

Lehilton L. C. Pedrosa

Rafael C. S. Schouery

Uéverton S. Souza

Algorithmica, 2021

2020

A strongly polynomial time algorithm for the maximum supply rate problem on trees.

[BibT_eX]

[DOI]

Koki Takayama

Theor. Comput. Sci., 2020

Complexity of the multi-service center problem.

[BibT_eX]

[DOI]

Takehiro Ito

Theor. Comput. Sci., 2020

Diameter of colorings under Kempe changes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Finding a path with two labels forbidden in group-labeled graphs.

[BibT_eX]

[DOI]

Yasushi Kawase

Yutaro Yamaguchi

J. Comb. Theory B, 2020

Linear min-max relation between the treewidth of an H-minor-free graph and its largest grid minor.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2020

On the number of edges in a graph with many two-hop disjoint paths.

[BibT_eX]

[DOI]

Koki Takayama

Discret. Appl. Math., 2020

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.

[BibT_eX]

[DOI]

Tom C. van der Zanden

Algorithmica, 2020

Shortest Reconfiguration of Colorings Under Kempe Changes.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

An FPT Algorithm for Minimum Additive Spanner Problem.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

The Steiner Problem for Count Matroids.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 31st International Workshop, 2020

Reconfiguration of Spanning Trees with Many or Few Leaves.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Two disjoint shortest paths problem with non-negative edge length.

[BibT_eX]

[DOI]

Ryo Sako

Oper. Res. Lett., 2019

Reconfiguration of maximum-weight b-matchings in a graph.

[BibT_eX]

[DOI]

J. Comb. Optim., 2019

An FPT Algorithm for Max-Cut Parameterized by Crossing Number.

[BibT_eX]

[DOI]

CoRR, 2019

Minimum-Cost b-Edge Dominating Sets on Trees.

[BibT_eX]

[DOI]

Algorithmica, 2019

The Perfect Matching Reconfiguration Problem.

[BibT_eX]

[DOI]

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

Parameterized Algorithms for Maximum Cut with Connectivity Constraints.

[BibT_eX]

[DOI]

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

2018

NP-hardness and fixed-parameter tractability of the minimum spanner problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

The parity Hamiltonian cycle problem.

[BibT_eX]

[DOI]

Discret. Math., 2018

Tight Approximation for Unconstrained XOS Maximization.

[BibT_eX]

[DOI]

Yasushi Kawase

Yutaro Yamaguchi

CoRR, 2018

2017

Randomized strategies for cardinality robustness in the knapsack problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Efficient stabilization of cooperative matching games.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

An algorithm for identifying cycle-plus-triangles graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Finding a Shortest Non-zero Path in Group-Labeled Graphs via Permanent Computation.

[BibT_eX]

[DOI]

Sho Toyooka

Algorithmica, 2017

The Directed Disjoint Shortest Paths Problem.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Tight Approximability of the Server Allocation Problem for Real-Time Applications.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects of Cloud Computing - Third International Workshop, 2017

2016

An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Covering Intersecting Bi-set Families under Matroid Constraints.

[BibT_eX]

[DOI]

Tamás Király

SIAM J. Discret. Math., 2016

Edge-disjoint odd cycles in 4-edge-connected graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

Improved max-flow min-cut algorithms in a Circular Disk Failure Model with application to a road network.

[BibT_eX]

[DOI]

Kensuke Otsuki

Eur. J. Oper. Res., 2016

2015

The Generalized Terminal Backup Problem.

[BibT_eX]

[DOI]

Attila Bernáth

Tatsuya Matsuoka

SIAM J. Discret. Math., 2015

The complexity of minimizing the difference of two M♮-convex set functions.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2015

Selecting vertex disjoint paths in plane graphs.

[BibT_eX]

[DOI]

Networks, 2015

Fence patrolling by mobile agents with distinct speeds.

[BibT_eX]

[DOI]

Akitoshi Kawamura

Distributed Comput., 2015

The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs.

[BibT_eX]

[DOI]

Comb., 2015

Finding a Path in Group-Labeled Graphs with Two Labels Forbidden.

[BibT_eX]

[DOI]

Yasushi Kawase

Yutaro Yamaguchi

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Triangle-free 2-matchings and M-concave functions on jump systems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2014

An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem.

[BibT_eX]

[DOI]

Stephan Kreutzer

Proceedings of the Symposium on Theory of Computing, 2014

The Generalized Terminal Backup Problem.

[BibT_eX]

[DOI]

Attila Bernáth

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Max-flow min-cut theorem and faster algorithms in a circular disk failure model.

[BibT_eX]

[DOI]

Kensuke Otsuki

Proceedings of the 2014 IEEE Conference on Computer Communications, 2014

2013

An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

Robust Matchings and Matroid Intersections.

[BibT_eX]

[DOI]

Ryo Fujita

Kazuhisa Makino

SIAM J. Discret. Math., 2013

2012

Testing the (s, t)-disconnectivity of graphs and digraphs.

[BibT_eX]

[DOI]

Yuichi Yoshida

Theor. Comput. Sci., 2012

Algorithms for Finding a Maximum Non-k-Linked Graph.

[BibT_eX]

[DOI]

Yuichi Yoshida

SIAM J. Discret. Math., 2012

The complexity of the node capacitated in-tree packing problem.

[BibT_eX]

[DOI]

Networks, 2012

Cone superadditivity of discrete convex functions.

[BibT_eX]

[DOI]

Robert Weismantel

Math. Program., 2012

A proof of Cunningham's conjecture on restricted subgraphs and jump systems.

[BibT_eX]

[DOI]

Jácint Szabó

J. Comb. Theory B, 2012

The disjoint paths problem in quadratic time.

[BibT_eX]

[DOI]

Bruce A. Reed

J. Comb. Theory B, 2012

Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2012

An algorithm for (n-3)-connectivity augmentation problem: Jump system approach.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2012

A linear time algorithm for the induced disjoint paths problem in planar graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

An algorithm for finding a maximum t-matching excluding complete partite subgraphs.

[BibT_eX]

[DOI]

Xin Yin

Discret. Optim., 2012

Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

List-coloring graphs without subdivisions and without immersions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

An Improved Algorithm for the Half-Disjoint Paths Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Breaking o(n1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Algorithms for Finding a Maximum Non-k-linked Graph.

[BibT_eX]

[DOI]

Yuichi Yoshida

Proceedings of the Algorithms - ESA 2011, 2011

2010

On shortest disjoint paths in planar graphs.

[BibT_eX]

[DOI]

Christian Sommer

Discret. Optim., 2010

A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs.

[BibT_eX]

[DOI]

Discret. Optim., 2010

Algorithms for finding an induced cycle in planar graphs.

[BibT_eX]

[DOI]

Comb., 2010

An Algorithm for Minimum Cost Arc-Connectivity Orientations.

[BibT_eX]

[DOI]

Satoru Iwata

Algorithmica, 2010

Improved Algorithm for the Half-Disjoint Paths Problem.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

An O(logn)-Approximation Algorithm for the Disjoint Paths Problem in Eulerian Planar Graphs and 4-Edge-Connected Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

Even factors, jump systems, and discrete convexity.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2009

Induced disjoint paths problem in a planar digraph.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2009

Algorithms for finding an induced cycle in planar graphs and bounded genus graphs.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

The Induced Disjoint Paths Problem.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2008

2007

Operations on M-Convex Functions on Jump Systems.

[BibT_eX]

[DOI]

Ken'ichiro Tanaka

SIAM J. Discret. Math., 2007

Induction of M-convex functions by linking systems.

[BibT_eX]

[DOI]