A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

DOI10.1016/J.IPL.2007.03.014MaRDI QIDQ2379975zbMATH OpenOpenAlexFDO

Authors Shin-Ichi Nakayama, Shigeru Masuyama

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.03.014

zbMATH Keywords

algorithmscomputational complexitycombinatorial problemminimal cutedge ranking

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• scientific article; zbMATH DE number 975401
• Edge ranking of graphs is hard
• On an edge ranking problem of trees and graphs
• scientific article; zbMATH DE number 437538
• Optimal edge ranking of complete bipartite graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs
• A linear time algorithm for longest (s,t)-paths in weighted outerplanar graphs
• Edge ranking of graphs is hard
• Finding minimum height elimination trees for interval graphs in polynomial time
• On an edge ranking problem of trees and graphs
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Optimal edge ranking of trees in polynomial time
• Optimal node ranking of tree in linear time
• Optimal node ranking of trees
• Rankings of Graphs

Cited in

(3)

• Facial edge ranking of plane graphs
• Finding the edge ranking number through vertex partitions
• Optimal edge ranking of complete bipartite graphs in polynomial time

This page was built for publication: A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

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