Geodesic
Algorithms for finding biclique covers of graphs with bounded pathwidth
Trudy Instituta matematiki, Tome 19 (2011) no. 2, pp. 69-81.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we present space-efficient algorithms for solving construction variants of biclique cover problems on graphs with bounded pathwidth. A biclique is a complete bipartite subgraph of a graph. Algorithms for solving the problem of finding a biclique cover with minimal degree and the problem of finding a biclique cover with minimal number of bicliques on this type of graphs in $O(n\log n)$ time with $O(\log n)$ additional memory are given. 
@article{TIMB_2011_19_2_a7,
     author = {V. V. Lepin and O. I. Duginov},
     title = {Algorithms for finding biclique covers of graphs with bounded pathwidth},
     journal = {Trudy Instituta matematiki},
     pages = {69--81},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2011_19_2_a7/}
}
TY  - JOUR
AU  - V. V. Lepin
AU  - O. I. Duginov
TI  - Algorithms for finding biclique covers of graphs with bounded pathwidth
JO  - Trudy Instituta matematiki
PY  - 2011
SP  - 69
EP  - 81
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2011_19_2_a7/
LA  - ru
ID  - TIMB_2011_19_2_a7
ER  - 
%0 Journal Article
%A V. V. Lepin
%A O. I. Duginov
%T Algorithms for finding biclique covers of graphs with bounded pathwidth
%J Trudy Instituta matematiki
%D 2011
%P 69-81
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2011_19_2_a7/
%G ru
%F TIMB_2011_19_2_a7
V. V. Lepin; O. I. Duginov. Algorithms for finding biclique covers of graphs with bounded pathwidth. Trudy Instituta matematiki, Tome 19 (2011) no. 2, pp. 69-81. http://geodesic.mathdoc.fr/item/TIMB_2011_19_2_a7/

[1] Blundo C., De Santis A., Stinson D.R., Vaccaro U., “Graph Decompositions and Secret Sharing Schemes”, J. Cryptology, 8:1 (1995), 39–64 | DOI | MR | Zbl

[2] Fishburn P.C., Hammer P.L., “Bipartite dimensions and bipartite degrees of graphs”, Discrete Math., 160 (1996), 127–148 | DOI | MR | Zbl

[3] Benzaken C., Boyd S., Hammer P.L., Simeone B., “Adjoints of pure bidirected graphs”, Congr. Numerantium, 39 (1983), 123–144 | MR | Zbl

[4] Crama Y., Hammer P.L., “Recognition of quadratic graphs and adjoints of bidirected graphs”, Ann. N.Y. Academy Sciences, 555 (1989), 140–149 | DOI | MR | Zbl

[5] Hammer P.L., Simeone B., “Quasimonotone Boolean functions and bistellar graphs”, Ann. Discrete Math., 9 (1980), 107–119 | DOI | MR | Zbl

[6] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[7] Günlük O., “A new min-vut max-flow ration for multicommodity flows”, Integer programming and combinatorial optimization, LNCS, 2337 (2006), 54–66 | DOI | MR

[8] Monson S.D., Pullman N.J., Rees R., “A survey of clique and biclique coverings and factorizations of $(0,1)$ — matrices”, Bull Institute Contrum. Appl., 14 (1995), 17–86 | MR | Zbl

[9] Nau D.S., Markowsky G., Woodburry M.A., Amos D.B., “A mathematical analysis of human leukocyte antigen serology”, Math. Biosci., 1978, 243–270 | DOI | MR | Zbl

[10] Lepin V.V., “Algoritmy dlya nakhozhdeniya multiklikovoi i biklikovoi stepeni posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 18:2 (2010), 60–78 | MR | Zbl

[11] Lepin V.V., “Lineinyi algoritm dlya vychisleniya chisla multiklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 17:1 (2009), 90–102 | Zbl

[12] Lepin V.V., “Lineinyi algoritm dlya vychisleniya chisla biklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Trudy Instituta matematiki, 16:2 (2008), 63–75 | MR | Zbl

[13] Robertson N., Seymour D., “Graph Minor II. Algorithmic aspects of tree width”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[14] Bodlaender H.L., “A linear-time algorithm for finding tree decompositions of small treewidth”, SIAM J. Comput., 25 (1996), 1305–1317 | DOI | MR | Zbl

[15] Cattell K., Dinneen M.J., Fellows M.R., “A simple linear-time algorithm for finding path-decompositions of small width”, Inform. Process. Lett., 57:4 (1996), 197–203 | DOI | MR | Zbl

[16] Perkovic' L., Reed B., “An Improved Algorithm for Finding Tree Decompositions of Small Width”, Lecture Notes In Computer Science, 1665, 1999, 148–154 | MR | Zbl

[17] Diaz J., Petit J., Serna M., “A survey of graph layout problems”, ACM Comput. Surveys, 34:3 (2002), 313–356 | DOI

[18] Kinnersley N.G., “The vertex separation number of a graph equals its path-width”, Inform. Process. Lett., 42:6 (1992), 345–350 | DOI | MR | Zbl

[19] Lepin V.V., “Reshenie zadach v klasse frontalno-ogranichennykh grafov”, Vestsi AN Belarusi. Ser. fiz.-mat. navuk, 1996, no. 3, 101–105 | MR | Zbl

[20] Bodlaender H.L., Kloks T., “Efficient and constructive algorithms for the pathwidth and treewidth of graphs”, J. Algorithms, 21 (1996), 358–402 | DOI | MR | Zbl

[21] Courcelle B., “The monadic second-order logic of graphs I: Recognizable sets of finite graphs”, Information and Computation, 85 (1990), 12–75 | DOI | MR | Zbl

[22] Wolle T., “A Framework for Network Reliability Problems on Graphs of Bounded Treewidth”, LNCS, 2518 (2002), 401–420 | MR

[23] Andreica M.I., “A Dynamic Programming Framework for Combinatorial Optimization Problems on Graphs with Bounded Pathwidth”, Proceedings of the IEEE International Conference on Automation, Quality and Testing, Robotics (THETA 16) (AQTR) – Poster Session, 2008, 120–125

[24] Lepin V.V., “Algoritmy resheniya zadach na grafakh s ogranichennoi putevoi shirinoi”, Trudy Instituta matematiki, 18:1 (2010), 53–71

[25] Bodlaender H.L., Telle J.A., “Space-efficient construction variants of dynamic programming”, Nordic Journal of Computing, 11:4 (2004), 374–385 | MR | Zbl