Rankings of graphs
Identifieur interne : 001572 ( Istex/Corpus ); précédent : 001571; suivant : 001573Rankings of graphs
Auteurs : H. L. Bodlaender ; J. S. Deogun ; K. Jansen ; T. Kloks ; D. Kratsch ; H. Müller ; Zs. TuzaSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1995.
Abstract
Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .
Url:
DOI: 10.1007/3-540-59071-4_56
Links to Exploration step
ISTEX:C10AA9E81094CD92694FF008D94185143272318FLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Rankings of graphs</title><author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name><affiliation><mods:affiliation>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hansb@cs.ruu.nl.</mods:affiliation></affiliation></author><author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA</mods:affiliation></affiliation></author><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name><affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name><affiliation><mods:affiliation>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven, The Netherlands</mods:affiliation></affiliation></author><author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name><affiliation><mods:affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</mods:affiliation></affiliation></author><author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name><affiliation><mods:affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</mods:affiliation></affiliation></author><author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name><affiliation><mods:affiliation>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest, Hungary</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C10AA9E81094CD92694FF008D94185143272318F</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1007/3-540-59071-4_56</idno><idno type="url">https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001572</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001572</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Rankings of graphs</title><author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name><affiliation><mods:affiliation>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hansb@cs.ruu.nl.</mods:affiliation></affiliation></author><author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name><affiliation><mods:affiliation>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA</mods:affiliation></affiliation></author><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name><affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier, Germany</mods:affiliation></affiliation></author><author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name><affiliation><mods:affiliation>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven, The Netherlands</mods:affiliation></affiliation></author><author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name><affiliation><mods:affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</mods:affiliation></affiliation></author><author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name><affiliation><mods:affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</mods:affiliation></affiliation></author><author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name><affiliation><mods:affiliation>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest, Hungary</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1995</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">C10AA9E81094CD92694FF008D94185143272318F</idno><idno type="DOI">10.1007/3-540-59071-4_56</idno><idno type="ChapterID">24</idno><idno type="ChapterID">Chap24</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>H. L. Bodlaender</name><affiliations><json:string>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands</json:string><json:string>E-mail: hansb@cs.ruu.nl.</json:string></affiliations></json:item><json:item><name>J. S. Deogun</name><affiliations><json:string>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA</json:string></affiliations></json:item><json:item><name>K. Jansen</name><affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier, Germany</json:string></affiliations></json:item><json:item><name>T. Kloks</name><affiliations><json:string>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven, The Netherlands</json:string></affiliations></json:item><json:item><name>D. Kratsch</name><affiliations><json:string>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</json:string></affiliations></json:item><json:item><name>H. Müller</name><affiliations><json:string>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</json:string></affiliations></json:item><json:item><name>Zs. Tuza</name><affiliations><json:string>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest, Hungary</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</abstract><qualityIndicators><score>6.98</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.28 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>887</abstractCharCount><pdfWordCount>6157</pdfWordCount><pdfCharCount>26811</pdfCharCount><pdfPageCount>13</pdfPageCount><abstractWordCount>165</abstractWordCount></qualityIndicators><title>Rankings of graphs</title><chapterId><json:string>24</json:string><json:string>Chap24</json:string></chapterId><refBibs><json:item><author><json:item><name>H,L Bodlaender</name></json:item></author><host><pages><last>234</last><first>226</first></pages><author></author><title>Proceedings of the 25th Annual ACM Symposium on Theory of Computing</title><publicationDate>1993</publicationDate></host><title>A linear time algorithm for finding tree-decompositions of small treewidth</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>H,L Bodlaender</name></json:item></author><host><volume>11</volume><pages><last>23</last><first>1</first></pages><author></author><title>Acta Cybernetica</title><publicationDate>1993</publicationDate></host><title>A tourist guide through treewidth</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>H,L Bodlaender</name></json:item><json:item><name>J,R Gilbert</name></json:item><json:item><name>H Hafsteinsson</name></json:item><json:item><name>T Kloks</name></json:item></author><host><pages><last>12</last><first>1</first></pages><author></author><title>Proceedings of the 17th International Workshop on Graph-Theoretic Concepts in Computer Science WG'91</title><publicationDate>1992</publicationDate></host><title>Approximating treewidth, pathwidth and minimum elimination tree height</title><publicationDate>1992</publicationDate></json:item><json:item><host><author><json:item><name>J,A Bondy</name></json:item><json:item><name>U,S R Murty</name></json:item></author><title>Graph Theory with Applications</title><publicationDate>1976</publicationDate></host></json:item><json:item><host><author><json:item><name>A Brandstadt</name></json:item></author><title>Special graph classes -a survey. Schriftenreihe des FB Mathematik</title><publicationDate>1991</publicationDate></host></json:item><json:item><author><json:item><name>P De La</name></json:item><json:item><name>R Torre</name></json:item><json:item><name>A,A Greenlaw</name></json:item><json:item><name> Sch</name></json:item><json:item><name> ~ffer</name></json:item></author><host><pages><last>144</last><first>138</first></pages><author></author><title>Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms</title><publicationDate>1993</publicationDate></host><title>Optimal edge ranking of trees in polynomial time</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>J,S Deogun</name></json:item><json:item><name>T Kloks</name></json:item><json:item><name>D Kratsch</name></json:item><json:item><name>H M~iller</name></json:item></author><host><pages><last>758</last><first>747</first></pages><author></author><title>Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science</title><publicationDate>1994</publicationDate></host><title>On vertex ranking for permutation and other graphs</title><publicationDate>1994</publicationDate></json:item><json:item><author><json:item><name>J,S Deogun</name></json:item><json:item><name>Y Peng</name></json:item></author><host><volume>79</volume><pages><last>28</last><first>19</first></pages><author></author><title>Congressus Numerantium</title><publicationDate>1990</publicationDate></host><title>Edge ranking of trees</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>I,S Duff</name></json:item><json:item><name>J,K Reid</name></json:item></author><host><volume>9</volume><pages><last>325</last><first>302</first></pages><author></author><title>ACM Transactions on Mathematical Software</title><publicationDate>1983</publicationDate></host><title>The multifrontal solution of indefinite sparse symmetric linear equations</title><publicationDate>1983</publicationDate></json:item><json:item><host><author><json:item><name>M,R Garey</name></json:item><json:item><name>D,S Johnson</name></json:item></author><title>Computers and Intractability: A Guide to the Theory of NP-completeness</title><publicationDate>1979</publicationDate></host></json:item><json:item><host><author><json:item><name>M,C Golumbic</name></json:item></author><title>Algorithmic Graph Theory and Perfect Graphs</title><publicationDate>1980</publicationDate></host></json:item><json:item><host><pages><last>229</last><first>225</first></pages><author><json:item><name>A,V Iyer</name></json:item><json:item><name>H,D Ratliff</name></json:item><json:item><name>G Vijayan</name></json:item></author><title>Optimal node ranking of trees. Information Processing Le'tters 28</title><publicationDate>1988</publicationDate></host></json:item><json:item><host><author><json:item><name>A,V Iyer</name></json:item><json:item><name>H,D Ratliff</name></json:item><json:item><name>G Vijayan</name></json:item></author><title>Parallel assembly of modular products--an analysis</title><publicationDate>1988</publicationDate></host></json:item><json:item><author><json:item><name>A,V Iyer</name></json:item><json:item><name>H,D Ratliff</name></json:item><json:item><name>G Vijayan</name></json:item></author><host><volume>30</volume><pages><last>52</last><first>43</first></pages><author></author><title>Discrete Applied Mathematics</title><publicationDate>1991</publicationDate></host><title>On an edge ranking problem of trees and graphs</title><publicationDate>1991</publicationDate></json:item><json:item><host><author><json:item><name>M Katchalski</name></json:item><json:item><name>W Mc</name></json:item><json:item><name>S Cuaig</name></json:item><json:item><name> Seager</name></json:item></author><title>Ordered colourings</title><publicationDate>1988</publicationDate></host></json:item><json:item><host><author><json:item><name>T,Kloks Treewidth</name></json:item></author><publicationDate>1993</publicationDate></host></json:item><json:item><author><json:item><name>C,E Leiserson</name></json:item></author><host><pages><last>281</last><first>270</first></pages><author></author><title>Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science</title><publicationDate>1980</publicationDate></host><title>Area efficient graph layouts for VLSI</title><publicationDate>1980</publicationDate></json:item><json:item><author><json:item><name>J,W H Liu</name></json:item></author><host><volume>11</volume><pages><last>172</last><first>134</first></pages><author></author><title>SIAM Journal of Matrix Analysis and Applications</title><publicationDate>1990</publicationDate></host><title>The role of elimination trees in sparse factorization</title><publicationDate>1990</publicationDate></json:item><json:item><author></author><host><author></author><title>Concurrent Design of Products and Processes</title><publicationDate>1989</publicationDate></host><publicationDate>1989</publicationDate></json:item><json:item><host><author><json:item><name>A Pothen</name></json:item></author><title>The complexity of optimal elimination trees</title><publicationDate>1988</publicationDate></host></json:item><json:item><author><json:item><name>N Robertson</name></json:item><json:item><name>P,D Seymour</name></json:item></author><host><volume>48</volume><pages><last>254</last><first>227</first></pages><author></author><title>Journal on Combinatorial Theory Series B</title><publicationDate>1990</publicationDate></host><title>Graph minors. IV. Tree-width and wellquasi-ordering</title><publicationDate>1990</publicationDate></json:item><json:item><author><json:item><name>N Robertson</name></json:item><json:item><name>P,D Seymour</name></json:item></author><host><volume>41</volume><pages><last>114</last><first>92</first></pages><author></author><title>Journal on Combinatorial Theory Series B</title><publicationDate>1986</publicationDate></host><title>Graph minors. V. Excluding a planar graph</title><publicationDate>1986</publicationDate></json:item><json:item><host><author><json:item><name>N Robertson</name></json:item><json:item><name>P,D Seymour</name></json:item></author><title>Graph minors. XIII. The disjoint paths problem</title><publicationDate>1986</publicationDate></host></json:item><json:item><author><json:item><name>A,A Schaffer</name></json:item></author><host><volume>33</volume><pages><last>96</last><first>91</first></pages><author></author><title>Information Processing Letters</title><publicationDate>1989</publicationDate></host><title>Optimal node ranking of trees in linear time</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>P Scheffler</name></json:item></author><host><author></author><title>3rd Twente Workshop on Graphs and Combinatorial Optimization , Memorandum No.1132</title><publicationDate>1993</publicationDate></host><title>Node ranking and searching on graphs (Abstract)</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>A Sen</name></json:item><json:item><name>H Deng</name></json:item><json:item><name>S Guha</name></json:item></author><host><volume>43</volume><pages><last>94</last><first>87</first></pages><author></author><title>Information Processing Letters</title><publicationDate>1992</publicationDate></host><title>On a graph partition problem with application to VLSI layout</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>E,S Wolk</name></json:item></author><host><volume>3</volume><pages><last>795</last><first>789</first></pages><author></author><title>Proceedings of the American Mathematical Society</title><publicationDate>1962</publicationDate></host><title>The comparability graph of a tree</title><publicationDate>1962</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1995</copyrightDate></serie><host><editor><json:item><name>Ernst W. Mayr</name></json:item><json:item><name>Gunther Schmidt</name></json:item><json:item><name>Gottfried Tinhofer</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item></subject><isbn><json:string>978-3-540-59071-2</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Graph-Theoretic Concepts in Computer Science</title><bookId><json:string>3540590714</json:string></bookId><volume>903</volume><pages><last>304</last><first>292</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-49183-5</json:string></eisbn><copyrightDate>1995</copyrightDate><doi><json:string>10.1007/3-540-59071-4</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1007/3-540-59071-4_56</json:string></doi><id>C10AA9E81094CD92694FF008D94185143272318F</id><score>0.22995374</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Rankings of graphs</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1995</p></availability><date>1995</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Rankings of graphs</title><author xml:id="author-1"><persName><forename type="first">H.</forename><surname>Bodlaender</surname></persName><email>hansb@cs.ruu.nl.</email><affiliation>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands</affiliation></author><author xml:id="author-2"><persName><forename type="first">J.</forename><surname>Deogun</surname></persName><affiliation>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA</affiliation></author><author xml:id="author-3"><persName><forename type="first">K.</forename><surname>Jansen</surname></persName><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier, Germany</affiliation></author><author xml:id="author-4"><persName><forename type="first">T.</forename><surname>Kloks</surname></persName><affiliation>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven, The Netherlands</affiliation></author><author xml:id="author-5"><persName><forename type="first">D.</forename><surname>Kratsch</surname></persName><affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</affiliation></author><author xml:id="author-6"><persName><forename type="first">H.</forename><surname>Müller</surname></persName><affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</affiliation></author><author xml:id="author-7"><persName><forename type="first">Zs.</forename><surname>Tuza</surname></persName><affiliation>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest, Hungary</affiliation></author></analytic><monogr><title level="m">Graph-Theoretic Concepts in Computer Science</title><title level="m" type="sub">20th International Workshop, WG '94 Herrsching, Germany, June 16–18, 1994 Proceedings</title><idno type="pISBN">978-3-540-59071-2</idno><idno type="eISBN">978-3-540-49183-5</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-59071-4</idno><idno type="book-ID">3540590714</idno><idno type="book-title-ID">42640</idno><idno type="book-volume-number">903</idno><idno type="book-chapter-count">32</idno><editor><persName><forename type="first">Ernst</forename><forename type="first">W.</forename><surname>Mayr</surname></persName></editor><editor><persName><forename type="first">Gunther</forename><surname>Schmidt</surname></persName></editor><editor><persName><forename type="first">Gottfried</forename><surname>Tinhofer</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-01"></date><biblScope unit="volume">903</biblScope><biblScope unit="page" from="292">292</biblScope><biblScope unit="page" to="304">304</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName></editor><biblScope><date>1995</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">C10AA9E81094CD92694FF008D94185143272318F</idno><idno type="DOI">10.1007/3-540-59071-4_56</idno><idno type="ChapterID">24</idno><idno type="ChapterID">Chap24</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1995</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>M17009</label><label>I1603X</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Combinatorics</term></item><item><term>Logics and Meanings of Programs</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-01">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540590714</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle><BookSubTitle>20th International Workshop, WG '94 Herrsching, Germany, June 16–18, 1994 Proceedings</BookSubTitle><BookVolumeNumber>903</BookVolumeNumber><BookDOI>10.1007/3-540-59071-4</BookDOI><BookTitleID>42640</BookTitleID><BookPrintISBN>978-3-540-59071-2</BookPrintISBN><BookElectronicISBN>978-3-540-49183-5</BookElectronicISBN><BookChapterCount>32</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="M17009" Priority="2" Type="Secondary">Combinatorics</BookSubject><BookSubject Code="I1603X" Priority="3" Type="Secondary">Logics and Meanings of Programs</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Ernst</GivenName><GivenName>W.</GivenName><FamilyName>Mayr</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gunther</GivenName><FamilyName>Schmidt</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gottfried</GivenName><FamilyName>Tinhofer</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap24" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>24</ChapterID><ChapterDOI>10.1007/3-540-59071-4_56</ChapterDOI><ChapterSequenceNumber>24</ChapterSequenceNumber><ChapterTitle Language="En">Rankings of graphs</ChapterTitle><ChapterFirstPage>292</ChapterFirstPage><ChapterLastPage>304</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>1</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540590714</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>H.</GivenName><GivenName>L.</GivenName><FamilyName>Bodlaender</FamilyName></AuthorName><Contact><Email>hansb@cs.ruu.nl.</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>J.</GivenName><GivenName>S.</GivenName><FamilyName>Deogun</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff3"><AuthorName DisplayOrder="Western"><GivenName>K.</GivenName><FamilyName>Jansen</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff4"><AuthorName DisplayOrder="Western"><GivenName>T.</GivenName><FamilyName>Kloks</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>D.</GivenName><FamilyName>Kratsch</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>H.</GivenName><FamilyName>Müller</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Zs.</GivenName><FamilyName>Tuza</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>Utrecht University</OrgName><OrgAddress><Postbox>P.O. Box 80.089</Postbox><Postcode>3508</Postcode><City>TB Utrecht</City><Country>The Netherlands</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Department of Computer Science and Engineering</OrgDivision><OrgName>University of Nebraska-Lincoln</OrgName><OrgAddress><Postcode>68588-0115</Postcode><City>Lincoln</City><State>NE</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>Fachbereich IV, Mathematik und Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postbox>Postfach 3825</Postbox><Postcode>D-54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgDivision>Department of Mathematics and Computing Science</OrgDivision><OrgName>Eindhoven University of Technology</OrgName><OrgAddress><Postbox>P.O.Box 513</Postbox><Postcode>5600</Postcode><City>MB Eindhoven</City><Country>The Netherlands</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Fakultät für Mathematik und Informatik</OrgDivision><OrgName>Friedrich-Schiller-Universität</OrgName><OrgAddress><Street>Universitätshochhaus</Street><Postcode>07740</Postcode><City>Jena</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgDivision>Computer and Automation Institute</OrgDivision><OrgName>Hungarian Academy of Sciences</OrgName><OrgAddress><Street>Kende u. 13-17</Street><Postcode>H-1111</Postcode><City>Budapest</City><Country>Hungary</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>A vertex (edge) coloring <Emphasis Type="Italic">c∶V</Emphasis> → {1, 2, ⋯, <Emphasis Type="Italic">t</Emphasis>} (<Emphasis Type="Italic">c′∶E</Emphasis> → {1, 2, ⋯, <Emphasis Type="Italic">t</Emphasis>}) of a graph <Emphasis Type="Italic">G=(V, E)</Emphasis> is a vertex (edge) <Emphasis Type="Italic">t-ranking</Emphasis> if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The <Emphasis Type="Italic">vertex ranking number</Emphasis> χ<Subscript><Emphasis Type="Italic">r</Emphasis></Subscript>(<Emphasis Type="Italic">G</Emphasis>) (<Emphasis Type="Italic">edge ranking number</Emphasis><InlineEquation ID="IE1"><InlineMediaObject><ImageObject FileRef="558_3540590714_Chapter_24_TeX2GIFIE1.gif" Format="GIF" Color="BlackWhite" Type="Linedraw" Rendition="HTML"></ImageObject></InlineMediaObject><EquationSource Format="TEX"> $$\chi '_r \left( G \right)$$ </EquationSource></InlineEquation>) is the smallest value of <Emphasis Type="Italic">t</Emphasis> such that <Emphasis Type="Italic">G</Emphasis> has a vertex (edge) <Emphasis Type="Italic">t</Emphasis>-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ<Subscript><Emphasis Type="Italic">r</Emphasis></Subscript>(<Emphasis Type="Italic">G</Emphasis>) can be computed in polynomial time when restricted to graphs with treewidth at most <Emphasis Type="Italic">k</Emphasis> for any fixed <Emphasis Type="Italic">k</Emphasis>. We characterize those graphs where the vertex ranking number χ<Subscript><Emphasis Type="Italic">r</Emphasis></Subscript> and the chromatic number χ coincide on all induced subgraphs, show that χ<Subscript><Emphasis Type="Italic">r</Emphasis></Subscript>(<Emphasis Type="Italic">G</Emphasis>)=χ(<Emphasis Type="Italic">G</Emphasis>) implies <Emphasis Type="Italic">χ(G)=ω(G)</Emphasis> (largest clique size) and give a formula for <InlineEquation ID="IE2"><InlineMediaObject><ImageObject FileRef="558_3540590714_Chapter_24_TeX2GIFIE2.gif" Format="GIF" Color="BlackWhite" Type="Linedraw" Rendition="HTML"></ImageObject></InlineMediaObject><EquationSource Format="TEX"> $$\chi '_r \left( {K_n } \right)$$ </EquationSource></InlineEquation>.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This author was partially supported by the ESPRIT Basic Research Actions of the EC under contract 7141 (project ALCOM II)</SimplePara></ArticleNote><ArticleNote Type="Misc"><SimplePara>This author was partially supported by the Office of Naval Research under Grant No. N0014-91-J-1693</SimplePara></ArticleNote><ArticleNote Type="Misc"><SimplePara>Research of this author was done while he visited IRISA, Rennes Cedex, France. This author was partially supported by Deutsche Forschungsgemeinschaft under Kr 1371/1-1</SimplePara></ArticleNote><ArticleNote Type="Misc"><SimplePara>This author was partially supported by the “OTKA” Research Fund of the Hungarian Academy of Sciences, Grant No. 2569</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Rankings of graphs</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Rankings of graphs</title></titleInfo><name type="personal"><namePart type="given">H.</namePart><namePart type="given">L.</namePart><namePart type="family">Bodlaender</namePart><affiliation>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands</affiliation><affiliation>E-mail: hansb@cs.ruu.nl.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="given">S.</namePart><namePart type="family">Deogun</namePart><affiliation>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">K.</namePart><namePart type="family">Jansen</namePart><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">T.</namePart><namePart type="family">Kloks</namePart><affiliation>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven, The Netherlands</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">D.</namePart><namePart type="family">Kratsch</namePart><affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">H.</namePart><namePart type="family">Müller</namePart><affiliation>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Zs.</namePart><namePart type="family">Tuza</namePart><affiliation>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest, Hungary</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-01</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</abstract><relatedItem type="host"><titleInfo><title>Graph-Theoretic Concepts in Computer Science</title><subTitle>20th International Workshop, WG '94 Herrsching, Germany, June 16–18, 1994 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Ernst</namePart><namePart type="given">W.</namePart><namePart type="family">Mayr</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gunther</namePart><namePart type="family">Schmidt</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gottfried</namePart><namePart type="family">Tinhofer</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1995</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic></subject><identifier type="DOI">10.1007/3-540-59071-4</identifier><identifier type="ISBN">978-3-540-59071-2</identifier><identifier type="eISBN">978-3-540-49183-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">42640</identifier><identifier type="BookID">3540590714</identifier><identifier type="BookChapterCount">32</identifier><identifier type="BookVolumeNumber">903</identifier><part><date>1995</date><detail type="volume"><number>903</number><caption>vol.</caption></detail><extent unit="pages"><start>292</start><end>304</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1995</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></relatedItem><identifier type="istex">C10AA9E81094CD92694FF008D94185143272318F</identifier><identifier type="DOI">10.1007/3-540-59071-4_56</identifier><identifier type="ChapterID">24</identifier><identifier type="ChapterID">Chap24</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1995</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001572 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001572 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:C10AA9E81094CD92694FF008D94185143272318F
|texte= Rankings of graphs
}}
| This area was generated with Dilib version V0.6.31. |  |