
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
A cactus is a connected graph that does not contain K_4  e as a minor. ...
read it

FixedParameter Algorithms for Graph Constraint Logic
Nondeterministic constraint logic (NCL) is a simple model of computatio...
read it

Finding a Maximum Minimal Separator: Graph Classes and FixedParameter Tractability
We study the problem of finding a maximum cardinality minimal separator ...
read it

Parameterized Complexity of (A,ℓ)Path Packing
Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)Path Pac...
read it

Market Pricing for Matroid Rank Valuations
In this paper, we study the problem of maximizing social welfare in comb...
read it

Computing the Largest Bond and the Maximum Connected Cut of a Graph
The cutset ∂(S) of a graph G=(V,E) is the set of edges that have one en...
read it

Reconfiguration of Spanning Trees with Many or Few Leaves
Let G be a graph and T_1,T_2 be two spanning trees of G. We say that T_1...
read it

Envyfree Relaxations for Goods, Chores, and Mixed Items
In fair division problems, we are given a set S of m items and a set N o...
read it

Weighted Trianglefree 2matching Problem with Edgedisjoint Forbidden Triangles
The weighted Tfree 2matching problem is the following problem: given a...
read it

LinearTime Recognition of DoubleThreshold Graphs
A graph G = (V,E) is a doublethreshold graph if there exist a vertexwe...
read it

Parameterized Algorithms for Maximum Cut with Connectivity Constraints
We study two variants of Maximum Cut, which we call Connected Maximum Cu...
read it

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Motivated by adjacency in perfect matching polytopes, we study the short...
read it

A Weighted Linear Matroid Parity Algorithm
The matroid parity (or matroid matching) problem, introduced as a common...
read it

Improved Analysis of HighestDegree Branching for Feedback Vertex Set
Recent empirical evaluations of exact algorithms for Feedback Vertex Set...
read it

Subgraph Isomorphism on Graph Classes that Exclude a Substructure
We study Subgraph Isomorphism on graph classes defined by a fixed forbid...
read it

The Perfect Matching Reconfiguration Problem
We study the perfect matching reconfiguration problem: Given two perfect...
read it

An FPT Algorithm for MaxCut Parameterized by Crossing Number
The MaxCut problem is known to be NPhard on general graphs, while it c...
read it

An FPT Algorithm for Minimum Additive Spanner Problem
For a positive integer t and a graph G, an additive tspanner of G is a ...
read it

Tight Approximation for Unconstrained XOS Maximization
A set function is called XOS if it can be represented by the maximum of ...
read it

Finding a Path in GroupLabeled Graphs with Two Labels Forbidden
The parity of the length of paths and cycles is a classical and wellstu...
read it
Yusuke Kobayashi
is this you? claim profile