Skip to main content
Top

2015 | OriginalPaper | Chapter

A Unified Approach for the Longest Path Problem on Some Tree-Like Graphs

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

In a graph, a maximal biconnected component is called a block. A graph is called a block (resp., cactus and probe block) graph if its every block is a clique (resp., an edge or cycle, and complete split graph). In this paper, we propose a unified approach for the longest path problem on block, cactus, and probe block graphs. As a result, the longest path problem can be solved in linear time on block and probe block graphs, and in quadrat time on cactus graphs.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
A Unified Approach for the Longest Path Problem on Some Tree-Like Graphs
Authors
Ang-Lin Dong
Sheng-Lung Peng
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-22204-2_13