Linear structure of bipartite permutation graphs and the longest path problem

DOI10.1016/J.IPL.2007.02.010MaRDI QIDQ2379947zbMATH OpenOpenAlexWikidataFDO

Authors Ryuhei Uehara, Gabriel Valiente

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.02.010

zbMATH Keywords

graph algorithmsgraph decompositionlinear time algorithmsbipartite permutation graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 2191997
• Bipartite permutation graphs
• scientific article; zbMATH DE number 1156661
• A linear algorithms for the two paths problem on permutation graphs
• A polynomial time algorithm for longest paths in biconvex graphs

Cites work

• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Bandwidth of chain graphs
• Bipartite permutation graphs
• Bipartite permutation graphs with application to the minimum buffer size problem
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient graph representations
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• Introduction to algorithms
• Node-Deletion Problems on Bipartite Graphs
• On approximating the longest path in a graph

Cited in

(18)

• A polynomial kernel for bipartite permutation vertex deletion
• The Longest Path Problem Is Polynomial on Interval Graphs
• Path eccentricity of graphs
• A polynomial time algorithm for longest paths in biconvex graphs
• A polynomial-time algorithm for finding critical nodes in bipartite permutation graphs
• A linear algorithms for the two paths problem on permutation graphs
• Labelled well-quasi-order for permutation classes
• Tractabilities and intractabilities on geometric intersection graphs
• The longest path problem is polynomial on cocomparability graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• Linear-time algorithms for counting independent sets in bipartite permutation graphs
• Labeling bipartite permutation graphs with a condition at distance two
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Rainbow vertex coloring bipartite graphs and chordal graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• The longest path problem has a polynomial solution on interval graphs
• Tropical paths in vertex-colored graphs
• The longest path problem is polynomial on cocomparability graphs

This page was built for publication: Linear structure of bipartite permutation graphs and the longest path problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379947)