Skip to main content
SpringerLink
Log in

Integral Mixed Unit Interval Graphs

  • Conference paper
Book cover Computing and Combinatorics (COCOON 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7434))

Included in the following conference series:

Abstract

We characterize graphs that have intersection representations using unit intervals with open or closed ends such that all ends of the intervals are integral in terms of infinitely many minimal forbidden induced subgraphs. Furthermore, we provide a quadratic-time algorithm that decides if a given interval graph admits such an intersection representation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Halldórsson, M.M., Patt-Shamir, B., Rawitz, D.: Online Scheduling with Interval Conflicts, in. In: Proceedings of the 28th Annual Conference on Theoretical Aspects of Computer Science (STACS), pp. 472–483 (2011)

    Google Scholar 

  2. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)

    Google Scholar 

  3. Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55, 99–104 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  4. Corneil, D.G., Olariu, S., Stewart, L.: The ultimate interval graph recognition algorithm? (Extended abstract). In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 175–180 (1998)

    Google Scholar 

  5. Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138, 371–379 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dourado, M.C., Le, V.B., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Mixed unit interval graphs. manuscript (2011)

    Google Scholar 

  7. Frankl, P., Maehara, H.: Open-interval graphs versus closed-interval graphs. Discrete Math. 63, 97–100 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific J. Math. 15, 835–855 (1965)

    MathSciNet  MATH  Google Scholar 

  9. Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139–152 (1995)

    Article  Google Scholar 

  10. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Amsterdam, The Netherlands. Annals of Discrete Mathematics, vol. 57 (2004)

    Google Scholar 

  11. Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Characterizing Minimal Interval Completions. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 236–247. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  12. Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31, 289–305 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Herrera de Figueiredo, C.M., Meidanis, J., Picinin de Mello, C.: A linear-time algorithm for proper interval graph recognition. Inf. Process. Lett. 56, 179–184 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kaplan, H., Shamir, R.: Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques. SIAM J. Comput. 25, 540–561 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kendall, D.G.: Incidence matrices, interval graphs, and seriation in archaeology. Pacific J. Math. 28, 565–570 (1969)

    MathSciNet  MATH  Google Scholar 

  16. Kratsch, D., Stewart, L.: Approximating Bandwidth by Mixing Layouts of Interval Graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 248–258. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  17. Krokhin, A.A., Jeavons, P.G., Jonsson, P.: The Complexity of Constraints on Intervals and Lengths. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. STACS 2002, pp. 443–454. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  18. Papadimitriou, C.H., Yannakakis, M.: Scheduling interval-ordered tasks. SIAM J. Comput. 8, 405–409 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  19. Rautenbach, D., Szwarcfiter, J.L.: Unit Interval Graphs - A Story with Open Ends. In: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011). Electronic Notes in Discrete Mathematics, vol. 38, pp. 737–742 (2011)

    Google Scholar 

  20. Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139–146. Academic Press (1969)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Universität Rostock, Rostock, Germany

    Van Bang Le

  2. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany

    Dieter Rautenbach

Authors
  1. Van Bang Le
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dieter Rautenbach
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of IT, University of Sydney, Building J12, 2006, Sydney, NSW, Australia

    Joachim Gudmundsson , Julián Mestre  & Taso Viglas ,  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Le, V.B., Rautenbach, D. (2012). Integral Mixed Unit Interval Graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds) Computing and Combinatorics. COCOON 2012. Lecture Notes in Computer Science, vol 7434. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32241-9_42

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-32241-9_42

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-32240-2

  • Online ISBN: 978-3-642-32241-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation