Yusuke Kobayashi

CoRR, October, 2025

Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs.

[BibT_eX]

[DOI]

CoRR, September, 2025

Finding spanning trees with perfect matchings.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2025

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

[BibT_eX]

[DOI]

Takashi Noguchi

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Pinwheel Covering.

[BibT_eX]

[DOI]

Akitoshi Kawamura

Yosuke Kusano

Proceedings of the Algorithms and Complexity - 14th International Conference, 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

Loss Minimization for Electrical Flows over Spanning Trees on Grids.

[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

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

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

EFX Allocations for Indivisible Chores: Matching-Based Approach.

[BibT_eX]

[DOI]

Ryoga Mahara

Souta Sakamoto

Proceedings of the Algorithmic Game Theory - 16th 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

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

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

[BibT_eX]

[DOI]

Discret. Optim., 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

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On Reachable Assignments Under Dichotomous Preferences.

[BibT_eX]

[DOI]

Proceedings of the PRIMA 2022: Principles and Practice of Multi-Agent Systems, 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

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Tight Approximation for Unconstrained XOS Maximization.

[BibT_eX]

[DOI]

Math. Oper. Res., 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

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

Linear-Time Recognition of Double-Threshold Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 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

Fixed-Parameter Algorithms for Graph Constraint Logic.

[BibT_eX]

[DOI]

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

The Steiner Problem for Count Matroids.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Market Pricing for Matroid Rank Valuations.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 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

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

[BibT_eX]

[DOI]

CoRR, 2019

The Perfect Matching Reconfiguration Problem.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Yoichi Iwata

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 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

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Diameter of Colorings Under Kempe Changes.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

Algorithms for Gerrymandering over Graphs.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019

2018

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 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

A Strongly Polynomial Time Algorithm for the Maximum Supply Rate Problem on Trees.

[BibT_eX]

[DOI]

Koki Takayama

Proceedings of the Frontiers in Algorithmics - 12th International Workshop, 2018

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

A weighted linear matroid parity algorithm.

[BibT_eX]

[DOI]

Satoru Iwata

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Complexity of the Multi-Service Center Problem.

[BibT_eX]

[DOI]

Takehiro Ito

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

The Directed Disjoint Shortest Paths Problem.

[BibT_eX]

[DOI]

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

Reconfiguration of Maximum-Weight b-Matchings in a Graph.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 23rd International Conference, 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

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

Efficient Stabilization of Cooperative Matching Games.

[BibT_eX]

[DOI]

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, 2016

Randomized Strategies for Cardinality Robustness in the Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics, 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

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

Minimum-Cost b -Edge Dominating Sets on Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 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

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

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 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

Edge-disjoint Odd Cycles in 4-edge-connected Graphs.

[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

Fence Patrolling by Mobile Agents with Distinct Speeds.

[BibT_eX]

[DOI]

Akitoshi Kawamura

Proceedings of the Algorithms and Computation - 23rd International Symposium, 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

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

The Edge Disjoint Paths Problem in Eulerian Graphs and 4-edge-connected Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Robust Matchings and Matroid Intersections.

[BibT_eX]

[DOI]

Ryo Fujita

Kazuhisa Makino

Proceedings of the Algorithms, 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

On Shortest Disjoint Paths in Planar Graphs.

[BibT_eX]

[DOI]

Christian Sommer

Proceedings of the Algorithms and Computation, 20th International Symposium, 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]