caa a22 4500 475778189 CHVBK 20180406123636.0 cr unu---uuuuu 170329e20001201xx s 000 0 eng 10.1007/s003730070002 doi (NATIONALLICENCE)springer-10.1007/s003730070002 Efficiently Recognizing the P 4-Structure of Trees and of Bipartite Graphs Without Short Cycles [Elektronische Daten] [Andreas Brandstädt, Van Bang Le, Stephan Olariu] Abstract.: A 4-uniform hypergraph represents the P 4-structure of a graph G if its hyperedges are the vertex sets of the P 4's in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P 4-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n 2) where n is the number of vertices. Springer-Verlag Tokyo, 2000 Brandstädt Andreas Universität Rostock, FB Informatik, D-18051 Rostock, Germany e-mail: ab@informatik.uni-rostock.de, DE aut Le Van Bang Universität Rostock, FB Informatik, D-18051 Rostock, Germany e-mail: le@informatik.uni-rostock.de, DE aut Olariu Stephan Department of Computer Science, Old Dominion University Norfolk, VA, USA e-mail: olariu@cs.odu.edu, US aut https://doi.org/10.1007/s003730070002 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s003730070002 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Brandstädt Andreas Universität Rostock, FB Informatik, D-18051 Rostock, Germany e-mail: ab@informatik.uni-rostock.de, DE aut NATIONALLICENCE 700 1- Le Van Bang Universität Rostock, FB Informatik, D-18051 Rostock, Germany e-mail: le@informatik.uni-rostock.de, DE aut NATIONALLICENCE 700 1- Olariu Stephan Department of Computer Science, Old Dominion University Norfolk, VA, USA e-mail: olariu@cs.odu.edu, US aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer