AbstractCai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time. We extend their result to bipartite graphs plus two edges. Our algorithm works on a depth-first-search spanning tree. This gives, as a byproduct, also a simplified solution to the one-edge case. It is a notoriously open question whether recognizing bipartite graphs plus k edges is a fixed-parameter tractable problem. The present result might support the affirmative conjecture
A graph G = (V, E) is a tolerance graph if each vertex v ∈ V can be associated with an interval of t...
A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of...
A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertic...
AbstractCai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in line...
Cai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time....
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized com...
AbstractA graph has linear clique-width at most k if it has a clique-width expression using at most ...
AbstractWe show that bisplit graphs can be recognized in O(n2) time. The previous best bound of O(mn...
Given a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positiv...
In this paper we give a recognition algorithm in O(n(n+m)) time for bipartite chain graphs, and dire...
We described a simple algorithm running in linear time for each xed constant k, that either establis...
Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that av...
We continue research into a well-studied family of problems that ask if the vertices of a graph can ...
A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two...
AbstractFor each constant k, we present a linear time algorithm that, given a planar graph G, either...
A graph G = (V, E) is a tolerance graph if each vertex v ∈ V can be associated with an interval of t...
A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of...
A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertic...
AbstractCai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in line...
Cai and Schieber (1997) proved that bipartite graphs plus one edge can be recognized in linear time....
We initiate the study of the Bipartite Contraction problem from the perspective of parameterized com...
AbstractA graph has linear clique-width at most k if it has a clique-width expression using at most ...
AbstractWe show that bisplit graphs can be recognized in O(n2) time. The previous best bound of O(mn...
Given a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positiv...
In this paper we give a recognition algorithm in O(n(n+m)) time for bipartite chain graphs, and dire...
We described a simple algorithm running in linear time for each xed constant k, that either establis...
Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that av...
We continue research into a well-studied family of problems that ask if the vertices of a graph can ...
A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two...
AbstractFor each constant k, we present a linear time algorithm that, given a planar graph G, either...
A graph G = (V, E) is a tolerance graph if each vertex v ∈ V can be associated with an interval of t...
A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of...
A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertic...
DOI
Add to ORKG